[알고리즘]BFS 개념 정리 / 문제 풀이

그래프를 가까운 노드부터 탐색하기

 

 

그래프 표현하는 법

1. queue로 구현이 가능하다. 

인접한 노드를 반복적으로 큐에 넣도록 작성한다.

DFS와 마찬가지로 2차원 배열이나 1차원 배열로 구현 가능하다. 

 

구현 과정

1. 탐색 시작 노드를 삽입하고 방문 처리

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입

3. 이 과정을 수행할 수 없을 때 까지 반복

 

 

파이썬에서는?

deque 라이브러리를 사용하는 것이 좋다. 

O(N)정도의 시간이 걸리며 대체로 DFS 보다 빠른 편이다.