[Baekjoon] 16947: 서울 지하철 2호선

문제

순환선의 특정 역과 순환선이 아닌 역 사이의 거리를 구하는 문제이다.

예를 들면 까치산은 순환선과 거리가 4, 도림천은 거리가 1이다.

 

풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q16947 {

    private static int n;

    private static List<List<Integer>> graph;
    private static boolean[] visited;
    private static int[] cycle;
    private static boolean[] check;
    private static int[] distances;

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

        n = Integer.parseInt(br.readLine());
        visited = new boolean[n + 1];
        cycle = new int[n + 1];
        check = new boolean[n + 1];
        distances = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        cycle[1] = 1;
        visited[1] = true;
        search(1);

        for (int i = 1; i <= n; i++) {
            if (!check[i]) {
                findDistance(i);
            }
        }

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

    public static void findDistance(int start) {
        Deque<int[]> dq = new ArrayDeque<>();
        boolean[] visited = new boolean[n + 1];
        dq.offerLast(new int[]{start, 0});

        while (!dq.isEmpty()) {
            int[] cur = dq.pollFirst();

            for (int next : graph.get(cur[0])) {
                if (visited[next]) {
                    continue;
                }

                if (check[next]) {
                    distances[start] = cur[1] + 1;
                    return;
                }

                visited[next] = true;
                dq.offerLast(new int[]{next, cur[1] + 1});
            }
        }
    }

    public static int search(int cur) {
        int result = -1;
        for (int next : graph.get(cur)) {
            if (next == cycle[cur]) {
                continue;
            }
            if (visited[next]) {
                check[cur] = true;
                return next;
            }
            cycle[next] = cur;
            visited[next] = true;
            int temp = search(next);
            if (temp != -1) {
                result = temp;
                if (result == cur) {
                    check[cur] = true;
                    return -1;
                }
                check[cur] = true;
            }
        }
        return result;
    }
}

결국 먼저 순환선이 무엇인지 먼저 찾아야 한다. 즉, 그래프의 사이클을 찾아야한다.

 

이 사이클을 찾는 유형은 전에 풀이했던 문제에도 포함되어 있는데, 못 풀어봤다면 한 번 풀어보자.

[Baekjoon] 9466: 텀 프로젝트

9466번: 텀 프로젝트

 

먼저 사이클의 조건 중 하나는 정점(vertex)가 3개 이상 있어야 한다는 것이다. 즉, 2개 이하라면 사이클이 형성될 수 없다.

위에 작성한 내 코드는 이미 방문했던 곳을 만나면 사이클일 거라는 추측으로 구현했다. 때문에 정점이 2개로 형성된 구간이 아니라는 것을 검증하는 로직이 추가되어야 한다.

 

검증 방식은 다음과 같다.

1. 다음 노드로 넘어갈 때 이전 노드를 계속 저장하면서 간다.
2. 다음 노드로 넘어간 후 다시 다음노드로 넘어갈 때, 이전 노드가 다음 노드와 같다면 건너뛴다.

 

이렇게 체크하여 사이클을 체크한 후 탐색을 빠져나온다.

 

그리고 사이클이 아닌 정점은 사이클을 만날 때 까지 BFS를 통해 탐색하며 거리를 구한다.

 

회고

이 문제는 사이클이 무조건 1개만 생기기 때문에 풀이가 좀 더 수월했다.

사이클이 여러 개인 문제를 풀어보고 싶다면 위에 링크한 문제를 풀어보자.