BOJ_1260) DFS와 BFS

# 문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

---

# 입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

---

# 출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

---

# 코드

#pragma warning(disable:4996)
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

// DFS를 stack을 이용해 풀기 위해
// first는 오름차순, second는 내림차순으로 정렬하는 함수
bool cmp(pair<int, int> p, pair<int, int> q) {
	if (p.first == q.first) return p.second > q.second;
	return p.first < q.first;
}

int main() {
	int N, M, V, s, e, i, cur;
	cin >> N >> M >> V;

	int *vDFS = new int[N+1]();
	int *vBFS = new int[N+1]();
	vector< pair<int, int> > lines;
	for (i = 0; i < M; i++) {
		cin >> s >> e;
		lines.push_back(make_pair(s, e));
		lines.push_back(make_pair(e, s));
	}

        // DFS
	sort(lines.begin(), lines.end(), cmp);
	stack<int> dfs;
	dfs.push(V);
	while (!dfs.empty()) {
		cur = dfs.top();
		if (vDFS[cur] == 0) {
			dfs.pop();
			vDFS[cur] = 1;
			cout << cur << " ";
			for (i = 0; i < 2 * M; i++) if (lines[i].first == cur) break;
			for (i; i < 2 * M; i++) {
				if (lines[i].first != cur) break;
				if (vDFS[lines[i].second] == 0) dfs.push(lines[i].second);
			}
		}
		else dfs.pop();
	}

	cout << "\n";

        // BFS
	sort(lines.begin(), lines.end());
	queue<int> bfs;
	bfs.push(V);
	vBFS[V] = 1;
	while (!bfs.empty()) {
		cur = bfs.front();
		cout << cur << " ";
		for (i = 0; i < 2 * M; i++) if (lines[i].first == cur) break;
		for (i; i < 2 * M; i++) {
			if (lines[i].first != cur) break;
			if (vBFS[lines[i].second] == 0) {
				vBFS[lines[i].second] = 1;
				bfs.push(lines[i].second);
			}
		}
		bfs.pop();
	}
}

DFS는 재귀함수로 푸는 방법도 있는데 여러 자료구조를 사용해보려고 stack을 이용했다.

---