[백준 Baekjoon] 16974번 서울 지하철 2호선 - JAVA

** 백준 Baekjoon 16974번 서울 지하철 2호선 - JAVA

---

문제 풀이

주어진 입력으로 그래프를 만들었을 때, 순환선(사이클)과의 거리를 각 역마다 출력하는 문제이다. 그래프에서 사이클을 찾는 것이 가장 중요하다. 사이클을 찾고 사이클에서 각 역이 얼마나 떨어져 있는지 찾아 문제를 해결하였다.

사이클을 찾는 여러 방법이 있을것이다. 각 역마다 사이클을 점검하는 방법을 처음 생각하였는데 그러면 비용이 클것 같아 한번에 사이클을 찾는 방법에 대해 생각해보았다. 빽트래킹과 유사하게 스택을 사용하여 문제를 해결하였다.

1. 각 역을 방문할 때에 스택에 추가한다.
2. 방금 전 방문한 곳이 아니며 이전에 방문한 경우 사이클이 발생한다.
   스택에 사이클의 시작점을 추가한다. 사이클을 체크할때 해당 역이 다시 나올때까지가 사이클이다. 사이클이 처음부터 발생하는 것이 아니라 중간부터 발생하는 경우를 체크하기 위함이다.
3. 사이클이 발생하면 더 이상 탐색을 하지 않고 종료한다.

사이클을 찾았으면 사이클의 각 역에서 bfs탐색을 하여 이외의 역들의 사이클로부터의 거리를 찾는다.

소스 코드

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

public class Main {
    public static int N;

    public static List<Integer>[] list;
    public static Stack<Integer> stack = new Stack<>();

    public static int[] arr;
    public static boolean[] visit, cycle;
    public static boolean isCycle = false;

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

        N = Integer.parseInt(br.readLine());

        list = new List[N + 1];
        arr = new int[N + 1];
        visit = new boolean[N + 1];
        cycle = new boolean[N + 1];

        for (int i = 0; i <= N; i++) {
            list[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());

            list[A].add(B);
            list[B].add(A);
        }

        dfs(1, 0);

        int circle = stack.pop();
        while (!stack.isEmpty()) {
            int n = stack.pop();
            cycle[n] = true;

            if (n == circle) {
                break;
            }
        }

        bfs();

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(arr[i] + " ");
        }

        System.out.println(sb);
    }

    public static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        visit = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            if (cycle[i]) {
                visit[i] = true;
                q.offer(i);
            }
        }

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int next : list[cur]) {
                if (!visit[next]) {
                    q.offer(next);
                    visit[next] = true;
                    arr[next] = arr[cur] + 1;
                }
            }
        }
    }

    public static void dfs(int cur, int prev) {
        visit[cur] = true;
        stack.push(cur);

        for (int next : list[cur]) {
            if (isCycle) {
                break;
            }

            if (visit[next] && next != prev) {
                isCycle = true;
                stack.push(next);
                return;
            } else if (!visit[next]){
                dfs(next, cur);
            }
        }

        if (!isCycle) {
            stack.pop();
        }
    }
}