자료구조/알고리즘 용도 정리
in Algorithm on Algorithm
Input data 개수에 따른 시간복잡도
너비 우선 탐색 (BFS)
그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제
미로를 빠져나가는 최단 거리를 구하는 문제
기본 골격
def bfs(graph, start_node):
2 visit = list()
3 queue = list()
4
5 queue.append(start_node)
6
7 while queue:
8 node = queue.pop(0)
9 if node not in visit:
10 visit.append(node)
11 queue.extend(graph[node])
12
13 return visit
