알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - BFS

05-2 너비 우선 탐색

- 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

- 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장함

- 시간 복잡도: O(V + E), V는 노드 수 E는 엣지 수

 

특징

- FIFO 탐색

- Queue 자료구조 이용

 

동작 방식

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

방문할 노드 체크를 위한 방문 배열, 그래프를 인접 리스트로 표현, 탐색을 위해 큐 사용

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

3. 큐 자료구조에 값이 없을 때까지 반복하기

 

 

구현

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True
    
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
        	if not (visited[i]):
            	queue.append(i)
                visited[i] = True

참고 사이트