IT/자료구조 & 알고리즘
[알고리즘] 너비 우선 탐색(BFS) (Python)
1. BFS란...? 한 단계씩 내려가면서 같은 레벨에 있는 노드들을 먼저 순회 2. 구현 전 생각정리 탐색할 그래프를 딕셔너리와 데크를 활용하여 구현해보자 need_visit 데크의 왼쪽에서 하나씩 node를 뽑아오며 탐색, 탐색할 때 그 node와 연결된 노드들을 need_visit 데크의 오른쪽에 추가해줌 3. 코드 구현 from collections import deque graph = dict() graph['A'] = deque(['B', 'C']) graph['B'] = deque(['A', 'D']) graph['C'] = deque(['A', 'G', 'H', 'I']) graph['D'] = deque(['B', 'E', 'F']) graph['E'] = deque(['D']) grap..
2021. 8. 8.