문제
그래프에서 탐색을 하는 방법에는 여러 가지가 존재한다. 깊이 우선 탐색(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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | #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;} |