[CPP] 2444번 - 너비 우선 탐색 복습 (BFS&DFS)

문제

https://www.acmicpc.net/problem/24444

BFS와 DFS?

그래프 탐색 알고리즘으로는 흔히 아는 BFS와 DFS가 있다.
BFS는 너비 우선 탐색이고, DFS는 깊이 우선 탐색이다.
1번과 연결된 노드가 2, 3이고 2와 연결된 노드가 4이라고 가정해 보자. BFS로 탐색하면 1 -> 2 -> 3 -> 4의 경로로 탐색할 것이다. DFS로 탐색하면 1 -> 2 -> 3 -> 4의 경로로 탐색할 것이다. (오름차순으로 방문한다고 가정했을 때) BFS는 같은 깊이의 노드를 모두 탐색하고 난 다음에 더 깊은 노드로 들어간다. DFS는 연결된 가장 깊은 노드로 먼저 이동한다.

BFS는 어떻게 구현되는가?

BFS는 주로 deque로 구현한다. 왜냐하면, deque는 push_back(), pop_front() 등의 연산을 지원하는데 이것이 BFS를 구현할 때 유용하기 때문이다.

• 최단 경로 탐색 등에 적합하며, 같은 깊이의 노드들을 먼저 탐색한다.
• 순서는 다음과 같다.

1. 시작 노드 (특정 노드)에서 탐색을 시작한다.
2. 시작 노드에서 연결된 모든 노드를 큐에 집어넣는다. (push_back())
3. 큐에 있는 노드를 하나씩 빼면서 그 노드에 연결된 노드를 모두 큐에 집어넣는다. (pop_front())
4. 큐가 다 빌 때까지 위의 과정을 반복한다.

DFS는 어떻게 구현되는가?

DFS는 주로 재귀로 구현한다. 왜냐하면 연결된 노드에 재귀적으로 방문하기 때문이다.

• 경로 탐색, 그래프의 연결 요소 확인 등에 적합하며, 하나의 경로를 끝까지 탐색한다.
• 순서는 다음과 같다.

1. 시작 노드 (특정 노드)에서 탐색을 시작한다.
2. 방문했음을 표시한다.
3. 연결된 노드들을 확인한다.
4. 연결된 노드에 방문한 적이 없으면, 연결된 노드들에서 순차적으로 DFS 함수(1~3번의 역할을 함)를 재귀적으로 호출한다.

 

* 위의 내용은 개인 공부용으로 적어놓은 글이기 때문에 틀린 내용이 기록되어있을 수 있습니다.

* 잘못된 내용이 있을 시 피드백주시면 반영하겠습니다. :)