그래프 순회

문제

그래프에서 탐색을 하는 방법에는 여러 가지가 존재한다. 깊이 우선 탐색(DFS; Depth First Search)과 너비 우선 탐색(BFS; Breadth First Search)가 대표적인 탐색 방법이다. 깊이 우선 탐색과 너비 우선 탐색을 하는 프로그램을 작성하시오.

이 문제에서 너비 우선 탐색이란 큐를 사용하여 한 번에 하나의 정점만 탐색을 하는 형태만을 생각한다.

---

입력

첫 번째 줄에 그래프의 정점의 개수 V, 간선의 개수 E, 그리고 시작 정점의 번호 S가 공백으로 분리되어 주어진다. (1 ≤ S ≤ V ≤ 20,000, 1 ≤ E ≤ 100,000)

두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보인 x, y가 공백으로 분리되어 주어진다. 이는 x와 y를 잇는 간선이 존재한다는 것을 의미한다. (1 ≤ x, y ≤ V, x ≠ y)

---

출력

첫 번째 줄에 정점 S에서 시작한 깊이 우선 탐색의 결과 중 오름차순으로 가장 빠른 것을 출력한다.

두 번째 줄에 정점 S에서 시작한 너비 우선 탐색의 결과 중 오름차순으로 가장 빠른 것을 출력한다.

---

힌트

입력 예제 1

5 6 2

1 2

1 3

2 4

3 4

3 5

4 5

출력 예제 1

2 1 3 4 5

2 1 4 3 5

입력 예제 2

5 4 1

1 2

1 3

2 5

3 4

출력 예제 2

1 2 5 3 4

1 2 3 5 4

#include <iostream> #include <queue> #include <stack> #include <algorithm> using namespace std; int V, E, S; //노드개수, 엣지게수, 시작점 int VisisB[20001]; //BFS 방문배열 int VisisD[20001]; //DFS 방문배열 vector<int> pathV[20001]; void BFS() { //너비 우선 탐색 queue<int> BFSQ; BFSQ.push(S); VisisB[S] = 1;//방문표기 while (!BFSQ.empty()) { int num = BFSQ.front(); cout << num << " "; BFSQ.pop(); vector<int>::iterator iter; for (iter = pathV[num].begin(); iter != pathV[num].end(); iter++) { if (VisisB[*iter] != 1) { VisisB[*iter] = 1;//방문표기 BFSQ.push(*iter); } } } cout << endl; } void DFS() { //깊이 우선 탐색 stack<int> DFSS; DFSS.push(S); while (!DFSS.empty()) { int num = DFSS.top(); if (VisisD[num] == 0) { cout << num << " "; VisisD[num] = 1;//방문표기 } vector<int>::iterator iter; for (iter = pathV[num].begin(); iter != pathV[num].end(); iter++) { if (VisisD[*iter] != 1) { DFSS.push(*iter); break; } } if (iter == pathV[num].end()) { DFSS.pop(); } } cout << endl; } int main() { //std::ifstream cin("input.txt"); cin >> V >> E >> S; int a, b; for (int i = 0; i < E; i++) { //간선 입력 cin >> a >> b; pathV[a].push_back(b); pathV[b].push_back(a); } for (int i = 1; i <= V; i++) { VisisB[i] = 0; VisisD[i] = 0; sort(pathV[i].begin(), pathV[i].end()); } DFS(); BFS(); //system("pause"); return 0; }