[Java] BOJ16947, 백준 - 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512MB	4549	2069	1335	42.802%

문제

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

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

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

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

 

입력

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

 

출력

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

 

<풀이>

이 문제는 그래프의 사이클을 구하는 법만 알면 쉽게 풀 수 있는 문제이다.

이 문제를 풀기 전 16929 문제를 통해 사이클 구하는 법에 익숙해지는 것을 추천한다.

 

일단 문제의 풀이를 크게 세 부분으로 나누면 다음과 같다.

1. 순환 노선 찾기
2. 순환 노선의 정보 저장하기
3. 순환 노선까지의 거리 구하기

 

1, 2. 순환 노선 찾기 / 정보 저장하기

사이클 경로를 효율적으로 구하기 위해서 DFS 알고리즘을 활용한다.

사이클이 되기 위한 최소 노드 수는 3개

주어지는 그래프에서 한 개의 사이클이 존재함이 보장되기 때문에 1번 역에서 출발하여 사이클을 구할 때까지 탐색한다.

사이클을 구하는 경우는 직전의 노드를 제외하고 이미 방문한 노드에 또 방문하는 경우이다.

 

*1번 노드가 사이클에 포함되는 경우

1부터 탐색을 시작하면 13471의 경로를 찾아서 사이클을 쉽게 찾을 수 있다.

 

*1번 노드가 사이클에 포함되지 않는 경우

이 경우에 그래프 탐색을 하면 1543674의 결과를 얻을 수 있는데, 그러면 그래프가 아닌 1 5 역까지 사이클에 포함되게 된다. 따라서, 재방문하게 되는 역을 기준으로 잡으면 사이클을 정확하게 구할 수 있게 된다.

지금 재방문하게되는 역은 역 4이다. 4를 기준으로 사이클을 찾게 되면 위의 탐색의 결과에서

1543674

43674 부분이 해당한다. 그러면 사이클에 해당하는 역인 4367을 정확히 구할 수 있게 된다.

 

3. 순환 노선까지의 거리 찾기

2번에서 순환 노선에 해당하는 역이 어떤 역인지에 대한 정보가 저장되었을 것이다.

순환 노선에 포함된 역을 기점으로 연결된 역들에 대해서 BFS를 통해 얼마나 거리가 떨어져있는지 구하면 된다.

 

 

소스코드

import java.io.*;
import java.util.*;

public class Main {

	private static boolean[] check;
	private static boolean[] cycle;
	private static int[] dist;
	private static ArrayList<Integer>[] adj;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 입력부
		int n = Integer.parseInt(br.readLine());
		check = new boolean[n + 1];
		cycle = new boolean[n + 1];
		dist = new int[n + 1];

		// 인접 리스트
		adj = new ArrayList[n + 1];
		for (int i = 0; i <= n; i++)
			adj[i] = new ArrayList<Integer>();

		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());

			adj[v1].add(v2);
			adj[v2].add(v1);
		}

		// 1. 순환 노선 찾기(DFS)
		dfs(0, 1, "");

		// 3. 순환 노선까지의 거리(BFS)
		check = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			if (cycle[i])
				bfs(i, 1);
		}

		for (int i = 1; i <= n; i++)
			System.out.print(dist[i] + " ");
	}

	// bfs를 통해서 cycle과의 거리를 계산
	private static void bfs(int v, int d) {
		for (int i = 0; i < adj[v].size(); i++) {
			int next = adj[v].get(i);
			// 사이클이 아니고 방문하지않은 노드일 경우
			if (!cycle[next] && !check[next]) {
				check[next] = true;
				dist[next] = d;
				bfs(next, d + 1);
			}
		}
	}

	// 어느 노드에서 왔는지
	private static void dfs(int pv, int v, String s) {
		check[v] = true;
		s += v + " ";

		// 현재 노드에서 방문할 수 있는 노드들을 탐색
		for (int i = 0; i < adj[v].size(); i++) {
			int next = adj[v].get(i);

			// 방문하지 않은 노드라면 탐색 진행
			if (!check[next]) {
				dfs(v, next, s);
			} else {
				// 방문했었던 노드인데 직전의 노드가 아니라면
				if (next != pv) {
					// 순환노선을 찾았다
					// 2. 순환 노선 저장
					cycle_check(next, s);
					return;
				}
			}
		}
	}

	private static void cycle_check(int fist_node, String s) {
		StringTokenizer st = new StringTokenizer(s);
		boolean start = false;
		while (st.hasMoreElements()) {
			int v = Integer.parseInt(st.nextToken());
			if (v == fist_node)
				start = true;
			if (start)
				cycle[v] = true;
		}
	}
}