DFS와 BFS (feat. 백준, 1260번)

DFS와 BFS
https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <map>
#include <set>
#include <queue>
using namespace std;
int N, M, V, cnt1, cnt2, ans1[1001], ans2[1001];
bool visit1[1001], visit2[1001];
map<int, set<int>> arr;
void dfs(register int v) {
	ans1[++cnt1] = v;
	visit1[v] = true;
	for (auto iter = arr[v].begin(); iter != arr[v].end(); ++iter)
		if (!visit1[*iter])
			dfs(*iter);
}
void bfs(register int v) {
	ans2[++cnt2] = v;
	visit2[v] = true;
	queue<int> q;
	q.push(v);
	while (!q.empty()) {
		auto x = q.front(); q.pop();
		for (auto iter = arr[x].begin(); iter != arr[x].end(); ++iter)
			if (!visit2[*iter])
				visit2[*iter] = true, ans2[++cnt2] = *iter, q.push(*iter);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> M >> V;
	memset(ans1, 0, sizeof(ans1[0]) * (N + 1));
	memset(ans2, 0, sizeof(ans2[0]) * (N + 1));
	memset(visit1, false, N + 1);
	memset(visit2, false, N + 1);
	for (register int m = 0, x, y; m < M; ++m)
		cin >> x >> y, arr[x].insert(y), arr[y].insert(x);
	cnt1 = cnt2 = 0;
	dfs(V);
	bfs(V);
	for (register int i = 1; i <= N; ++i) {
		if (!ans1[i])
			break;
		cout << ans1[i] << " ";
	}
	cout << "\n";
	for (register int i = 1; i <= N; ++i) {
		if (!ans2[i])
			break;
		cout << ans2[i] << " ";
	}
	return 0;
}
// *&)*@*

1. DFS와 BFS간 구별을 위해 사용하는 변수를 모두 나누었습니다. (입력받은 정보 제외)
2. 문제는 이전의 DFS, BFS 연습문제처럼 해당 노드(1번 노드, 3번 노드 등)가 몇번째인가? 를 묻는 문제가 아니라 1번째는 X노드, 2번째는 Y노드, 3번째는 Z노드 처럼 순서별 노드 번호를 출력하는 문제입니다.