Problem 16947

서울 지하철 2호선

문제

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, …, N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

문제 링크

https://www.acmicpc.net/problem/16947

예제 입력 1

4
1 3
4 3
4 2
1 2

예제 출력 1

0 0 0 0

예제 입력 2

6
1 2
3 4
6 4
2 3
1 3
3 5

예제 출력 2

0 0 0 1 1 2

예제 입력 3

51
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 1
11 44
44 45
45 46
46 47
34 48
48 49
49 50
50 51

예제 출력 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 1 2 3 4

예제 입력 4

38
1 2
2 3
3 4
4 5
5 6
6 1
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38

예제 출력 4

0 0 0 0 0 0 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

solve

주어진 그래프에서 사이클에 포함되는 노드를 구하고 모든 노드에서 각각 사이클과의 거리를 구하는 문제이다.
dfs를 통해 각 노드별로 사이클에 포함되는지 여부를 구하고
- dfs의 리턴값을 다음과 같이 정의한다.
  - -2 : 사이클을 찾았지만 사이클에 포함되지 않는 경우
    - -1 : 사이클을 찾지 못한 경우
    - 0 ~ n - 1 : 사이클을 찾은 경우 (사이클의 시작 인덱스)
- 직전에 방문한 노드로는 탐색을 하지 않고 처음으로 방문했던 노드를 다시 만난다면 사이클의 시작점이다. 이 경우 사이클에 포함시키고 사이클의 시작점을 리턴한다.
  - 이때 리턴을 하다가 현재 노드와 리턴값(사이클의 시작점)이 같아진다면 여기부터는 사이클이 아니므로 -2를 리턴한다.
- check배열에 ( 0 : 방문 x , 1 : 방문, 2 : 사이클 )을 기록한다.
bfs를 통해 각 노드와 사이클과의 거리를 구하면 된다.
- 모든 노드를 확인하여 사이클에 포함되었다면 dist에 사이클과의 거리 0을 기록하고 큐에 push한다.
- 사이클에 포함되지 않는다면 -1로 초기화한다.
- 이후 bfs를 수행하며 다음 노드가 사이클에 포함되어있지 않다면(dist[i]가 -1 이라면) 큐에 push하고 거리를 1증가시킨다.

코드 설명

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;
vector<int> a[3001];
int dist[3001];
int check[3001]; // 0 : 방문 x , 1 : 방문, 2 : 사이클

int dfs(int node, int p) // p : 이전 노드
{	// -2 : 사이클을 찾았지만 사이클에 포함되지 않는 경우
	// -1 : 사이클을 찾지 못한 경우
	// 0 ~ n - 1 : 사이클을 찾은 경우 (사이클의 시작 인덱스)

	if (check[node] == 1) return node; // 처음으로 방문했던 노드를 다시 만났다면 사이클의 시작점
	check[node] = 1; // 방문 처리
	for (int i = 0; i < a[node].size(); i++)
	{
		int next = a[node][i];
		if (next != p) // 이전 노드로는 가지 않음
		{
			int res = dfs(next, node);
			if (res == -2) return -2;
			if (res >= 0) // 사이클을 찾은 경우(사이클 시작 노드)
			{
				check[node] = 2; // 사이클에 포함
				if (node == res) return -2; // 사이클의 시작점을 찾았다면 여기부턴 사이클이 아님
				else return res; // 사이클 시작 노드를 리턴
			}
		}
	}
	return -1; // 사이클을 찾지 못함
}

int main(void)
{
	int n; // 역의 개수
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}

	dfs(1, -1); // dfs로 사이클의 포함여부를 모두 구함

	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
		if (check[i] == 2) // 사이클에 포함된 경우
		{
			dist[i] = 0; // 사이클과의 거리는 0
			q.push(i);
		}
		else
		{
			dist[i] = -1;
		}
	}

	while (!q.empty()) // bfs로 사이클과의 거리를 구함
	{
		int node = q.front();
		q.pop();
		for (int i = 0; i < a[node].size(); i++)
		{
			int next = a[node][i];
			if (dist[next] == -1) // 다음 노드가 사이클에 포함되어있지 않다면
			{
				q.push(next);
				dist[next] = dist[node] + 1;
			}
		}
	}
	for (int i = 1; i <= n; i++)
		cout << dist[i] << ' ';
	cout << '\n';
}

백준 16947번 서울 지하철 2호선

Baekjoon algorithm