너비우선탐색

너비 우선 탐색(Breath First Search, BFS)

📔 너비 우선 탐색(BFS) 이란 너비를 우선으로 하여 탐색을 수행하는 알고리즘 최단경로(최단길이)를 찾을 때 주로 사용한다. 큐와 그래프로 해결한다. (파이썬에서는 데크(deque)를 쓰면 속도가 빠름) 📔 너비 우선 탐색(BFS) 구현 from collections import deque # 인접리스트 # 노드: 1,2,3,4,5,6,7 n = 7 adj = {x: [] for x in range(1, n + 1)} edges = [ [1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7] ] # 무방향 그래프이므로 반대쪽도 성립 for edge in edges: s, e = edge adj[s].append(e) adj[e].append(s) print(adj) # bfs..