16947번 서울 지하철 2호선

DFS을 사용하여 그래프의 사이클을 찾고, BFS를 이용하여 거리를 찾아가는 문제이다.
도움이 많이되는 문제라고 생각한다. 1) 사이클에 해당하는 점들을 기억하는 방법을 알 수 있었고, 2)여러 문제를 풀면서 DFS에서 반환형을 void로 할지, int로 할지 계속 고민이 많아졌다. 해당 문제가 그 궁금증을 해결해 줄 것이라고 생각한다.
재귀에서 돌아올 때, 해당 재귀가 끝나는 값을 가져올 필요가 있으면 int 형을, 단순히 check만 필요할때는 void를 사용해야겠다. 쓰고보니 너무 당연한 말이다.
아무튼 다시 한번 보면서 return 값에 대해 생각을 정리해야겠다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int n;
int dist[3001];
int ch[3001];
vector<int> graph[3001];
int DFS(int now, int pre) {
	if (ch[now]==1) {
		return now;
	}
	else {
		ch[now] = 1;
		for (int i = 0; i < graph[now].size(); i++) {
			if (graph[now][i] == pre) continue;
			int res = DFS(graph[now][i], now);
			if (res == -2) return -2;
			if (res >= 0) {
				ch[now] = 2;
				if (now == res) return -2;
				else return res;
			}
		}
		return -1;
	}
}
int main() {
	//freopen("in1.txt", "rt", stdin);
	cin >> n;
	int a, b;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	//ch[1] = 1;
	DFS(1, 0);
	queue<int> Q;
	for (int i = 1; i <= n; i++) {
		if (ch[i] == 2) {
			dist[i] = 0;
			Q.push(i);
		}
		else dist[i] = -1;
	}
	while (!Q.empty()) {
		int tmp = Q.front();
		Q.pop();
		for (int i = 0; i < graph[tmp].size(); i++) {
			if (dist[graph[tmp][i]] == -1) {
				Q.push(graph[tmp][i]);
				dist[graph[tmp][i]] = dist[tmp] + 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << " ";
		//cout << ch[i] << " ";
	}
	return 0;
}