[Algorithm] BFS, 너비 우선 탐색

BFS, 너비 우선 탐색

* 너비 우선 탐색

임의의 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

임의의 루트 노드로부터 가장 가까운 노드를 먼저 탐색하고, 멀리 있는 것을 가장 나중에 탐색한다.

어떤 노드를 탐색했는 지를 반드시 기록해야 하며, 일반적으로 큐를 사용해 선입선출을 원칙으로 탐색한다.

 

1) 깊이가 1인 노드, 2인 노드, 3인 노드... 를 반복하며 탐색하고, 방문한 노드는 큐에 기록한다.

2) 큐에 들어있는 노드를 하나씩 꺼내고 인접해 있는 노드를 차례로 방문한다.

3) 큐에 있는 노드가 없어질 때까지 반복한다.

 

* 적용 예시

• 두 노드 사이의 최단 경로를 알고싶을 때
• 임의의 경로를 찾고자 할 때

 

* 탐색 과정

 

---

- 연습 문제

www.acmicpc.net/problem/1260

programmers.co.kr/learn/courses/30/lessons/43162

 

---

[참고한 곳] gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html