[백준 16947] 서울 지하철 2호선

문제 링크 => 16947번: 서울 지하철 2호선 (acmicpc.net)

16947번: 서울 지하철 2호선

---

BFS + DFS 짬뽕 문제이다.

 

이 문제는 역과 역 사이의 방향이 양방향으로 주어졌고 핵심은 순환이 되는 순환선 즉, 한 역에서 출발해서 계속 가다가 다시 출발한 역으로 돌아올 수 있는 노선을 구분짓는 것이다.

 

1. 순환선은 DFS 를 활용하여 판별하였다.

 

판별 방법은 한 역에서 출발해서 계속 가다가 다시 출발한 역으로 돌아올 수 있다는 점을 다음과 같이 해결하였다.

=> 적어도 이동한 횟수가 2를 초과해서 다시 돌아올 경우 해당 역은 순환선에 포함된다.

 

2. 순환선과 임의의 역 사이의 거리는 BFS 를 활용하여 판별하였다.

 

일단 순환선에 해당하는 역은 항상 거리가 0이고 그 외에는 0이 아니라는 것은 분명하다.

 

따라서 거리가 0이 아닌 역들만 BFS 를 돌려서 Queue 에 노드와 이동한 거리를 push하고 pop을 반복하고 순환선에 해당하는 역에 도착하게 된다면 현재까지 이동한 거리가 결국 순환선과 임의의 역 사이의 거리가 되므로 거리를 변경해준다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define MOD 1000000009
#define ll long long

using namespace std;

int N;
int result[3001];
bool visited[3001];
vector<int> v[3001];

void set_Result(int n) {
	for (int i = 1; i <= n; i++) result[i] = INF;
}

void init(int n) {
	for (int i = 1; i <= n; i++) visited[i] = false;
}

void find_Circulation(int x, int first,int dist) {
	if (visited[x]) {
		if (x == first && dist > 2) {
			result[x] = 0;
		}
		return;
	}
	visited[x] = true;
	for (int i = 0; i < v[x].size(); i++) find_Circulation(v[x][i], first, dist+1);
}

void bfs(int start) {
	queue<pair<int,int>> q;
	q.push({ start,0 });
	visited[start] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int dist = q.front().second;
		q.pop();
		if (result[x]==0) {
			result[start] = dist;
			return;
		}
		for (int i = 0; i < v[x].size(); i++) {
			int nextX = v[x][i];
			if (!visited[nextX]) {
				visited[nextX] = true;
				q.push({ nextX,dist + 1 });
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	
	set_Result(N);

	for (int i = 1; i <= N; i++) {
		init(N);
		find_Circulation(i, i, 0);
	}

	for (int i = 1; i <= N; i++) {
		if (result[i] != 0) {
			init(N);
			bfs(i);
		}
	}

	for (int i = 1; i <= N; i++) cout << result[i] << " ";

	return 0;
}