[2021 하계 모각코] 5차시

너비 우선 탐색 알고리즘

 

그래프 탐색 시 탐색 방법 중 하나이다. 그래프 탐색은 하나의 정점에서 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것이다.

​

루트노드 또는 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법으로 탐색 시에 너비를 우선으로 하는 알고리즘이다.

즉 시작 노드에서 가까운 노드를 먼저 방문하고 멀리 떨어져있는 노드를 나중에 방문하는 순회 방법이다.

너비우선탐색은 최단 경로를 찾거나 임의의 경로를 찾고자 할 때 사용한다.

​

노드에 대한 방문 여부를 검사해야하기 때문에 큐 자료구조를 사용하여 방문한 노드들을 저장하고 꺼낼 수 있도록 한다. 큐는 선입선출로서 방문한 노드를 삽입하고 선출 노드의 인접노드를 삽입함으로써 사용한다.

재귀적으로 동작하지 않기 때문에 반복문을 사용하여 방문 여부를 확인하며 구현한다.

 

 

---

 

시간 복잡도

​

그래프가 어떻게 표현됐는지에 따라 시간복잡도가 달라진다.

​

인접 리스트 그래프 : O(N+E)

인접 행렬 그래프 : O(N^2)

​

간선이 적을 경우 인접 리스트를 사용하는 것이 유리한다.

 

---

https://github.com/miraekwak/BOJ/blob/main/2606.py

GitHub - miraekwak/BOJ