문제

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

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

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

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

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

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

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

접근

순환선에 속하는 모든 역들을 구하기만 하면 거리를 구하는 건 어렵지 않을 거라고 생각했다. 순환선에 속하는 역들은 당연히 거리가 그냥 0일 것이고, 순환선에 속하지 않는 역의 경우에는 가장 가까운 순환역에 도달할 때까지 탐색해보면 거리가 금방 나오니까.

순환선에 속하는 역들을 어떻게 구할 것이냐가 문제였다. 방향 그래프면 그냥 방향에 따라서 탐색하다가 이미 지나온 역에 다시 도달했다면 사이클이 발생했음을 인지할 수가 있다. 반면 이 문제에서 다루는 그래프는 무방향이지만 한 방향으로만 탐색을 해야 사이클을 판별할 수가 있는데, (왔던 길을 되돌아가는 건 의미가 없으니...) 그 방향을 어떻게 지정해줘야 할지를 조금 고민했다.

dfs를 통해 탐색을 진행하다가 이미 지나온 노드에 다시 방문했다면,
1. 직전에 방문한 노드인 경우 (사이클 아님)
2. 사이클이 발견된 경우
이 두 가지 중 하나이기 때문에 1번인 경우에는 이미 방문한 경로이니 스킵하고, 2번인 경우에만 사이클로 판별하고 탐색을 종료하도록 구현했다.

그리고 지선 역에서부터 순환선까지의 거리는 해당 지선 역에서 가장 가까운 순환역이 발견될 때까지 너비를 넓혀가며 탐색해야만 최소 거리임이 보장될 것이므로 bfs를 통해 탐색을 해서 구해야 할 것이다.

구현

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

class Main {
    static List<Integer>[] graph;
    static List<Integer> innerCircles = new ArrayList<>();
    static int[] answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        graph = new List[N + 1];
        answer = new int[N + 1];
        Arrays.fill(answer, -1);

        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        
        // 순환선에 속하는 역 모두 찾기
        List<Integer> history = new ArrayList<>();
        history.add(1);
        dfs(history);

		// 순환선에 속하는 역에 대해 거리를 0으로 설정
        for (int station : innerCircles) {
            answer[station] = 0;
        }

		// 순환선에 속하는 역인데 간선이 2개보다 많다면 해당 역에서 뻗어나오는 지선이 존재한다는 뜻.
        // -> bfs를 통해 지선에 대한 탐색 수행
        for (int station : innerCircles) {
            if (graph[station].size() > 2) {
                bfs(station);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(answer[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

    private static void dfs(List<Integer> history) {
        if (!innerCircles.isEmpty()) {
            return;
        }
        int curr = history.get(history.size() - 1);
        for (int neighbor : graph[curr]) {
        	// 이미 방문한 노드에 다시 방문했다면?
            if (history.contains(neighbor)) {
            	// 직전에 방문한 노드인 경우 이미 탐색한 경로이므로 스킵
                if (history.get(history.size() - 2) == neighbor) {
                    continue;
                }
                // 직전 방문 노드가 아닌 경우 -> 사이클 발견
                for (int i = history.indexOf(neighbor); i < history.size(); i++) {
                    innerCircles.add(history.get(i));
                }
                return;
            }
            
            // 방문한 적 없는 노드라면 히스토리에 추가하고 계속해서 dfs 탐색 수행
            history.add(neighbor);
            dfs(history);
            // 방문한 적 없는 노드에 대해 dfs를 종료했다면 해당 노드는 다시 히스토리에서 삭제
            history.remove(history.size() - 1);
        }
    }

    private static void bfs(int start) {
        Queue<int[]> q = new LinkedList<>();
        // {노드 번호, 순환선에 속하는 역과의 거리}
        q.offer(new int[] {start, 0});
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            
            for (int neighbor : graph[curr[0]]) {
            	// 이미 거리 구한 역이면 스킵
                if (answer[neighbor] >= 0)   continue;
                // curr에서 한 번 더 가야 neighbor에 도달 가능
                answer[neighbor] = curr[1] + 1;
                // 너비를 넓혀가며 bfs를 계속 수행
                q.offer(new int[] {neighbor, curr[1] + 1});
            }
        }
    }
}