ALGORITHMS/BFS vs DFS (3) 썸네일형 리스트형 when to BFS vs DFS BFS - 최단경로/미로찾기 --> 거리 구할때 GRAPH[nx][ny] = GRAPH[x][y] + 1 업데이트 --> return GRAPH[N-1][M-1] inside WHILE loop - BFS로 모든 노드 방문하는 법 --> nested for loop and call BFS() - Good time complexity but bad space complexity DFS - 완전탐색 (Brute Force Search All) - 조합/순열 --> 모든 경우의 수 [모든 노드 방문] - BACKTRACKING (with some condition) - Good space complexity but bad time complexity (recursion & must visit all nodes) BFS vs DFS [adj. matrix] * USE DEQUE instead of queue # BFS vs DFS [adj matrix] # https://sexy-developer.tistory.com/54 #1. BFS ------------------------------------------------------------------------------------- def bfs(graph, start): visited = [False] * len(graph) answer = [] queue = [start] visited[start] = True while queue: node = queue.pop(0) answer.append(node) for i in range(len(graph[node])): if graph[node][i] .. BFS vs DFS [adj. list] from collections import deque #1. ADJACENCY MATRIX REPRESENTATION --> MUST SORT FIRST WHEN CONSTRUCTING GRAPH 2. USE DEFAULT DICT #2. DFS --> STACK or RECURSION #3. BFS --> QUEUE (DEQUE) --> CANNOT USE RECURSION #4. APPEND (for adj in node[cur]) vs EXTEND (no looping required) graph1 = { 'A': ['B'], 'B': ['A', 'C', 'H'], 'C': ['B', 'D'], 'D': ['C', 'E', 'G'], 'E': ['D', 'F'], 'F': ['E'], 'G': ['.. 이전 1 다음