[JAVA] 백준 16947번: 서울 지하철 2호선 ( 초급 2-45 ) - fail

문제

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

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

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

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

입력

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

출력

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

 

문제 풀이

이 문제는 2개의 step으로 나눠서 문제를 해결하면 된다.

1. 사이클에 포함되는 역 확인

2. 사이클에 포함되지 않는 역은 사이클과 몇 정거장 떨어져 있는지 확인

 

1. 사이클에 포함되는 역 확인

경로가 중요한 문제이기 때문에 dfs를 이용하여 문제를 해결하였다.

시작 경로는 무조건 1번 역으로 지정하였다.

 

1번 역 부터 시작하여, 이어지는 역을 차례대로 방문하면서 stack에 집어 넣는다.

더 이상 이어지는 역이 없을 경우 이전 분기점까지 pop을 한다.

분기점 부터 방문하지 않은 다음 역을 계속해서 방문하고, 똑같은 역을 두 번 방문한 경우가 사이클을 한번 돈 경우가 되는 것이다.

1 -> 2 -> 3 -> 1 (사이클 확인)

stack에 쌓여있는 1, 2, 3 을 역순으로 확인 하면서 1번역이 나올 때 까지 (똑같은 역을 두번 방문한 지점이 사이클의 시작점이자 끝 지점이다.) isCycle = true; 로 표시해준다.

 

이제는 사이클로 부터 bfs를 이용하여 사이클이 아닌 지점이 사이클로 부터 얼마나 떨어져 있는지를 확인하면 된다.

 

 

import java.beans.Visibility;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class baekjoon16947_3 {
    private static ArrayList<ArrayList<Integer>> info;
    private static int[] distInfo;
    private static boolean[] visit;
    private static boolean[] isCycle;
    private static int n;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        distInfo = new int[n + 1];
        visit = new boolean[n + 1];
        isCycle = new boolean[n + 1];
        info = new ArrayList<>();

        for (int i = 0; i < n + 1; i++) {
            info.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            info.get(from).add(to);
            info.get(to).add(from);
        }

        Stack<Integer> stack = new Stack<>();
        stack.add(1);
        visit[1] = true;
        findCycle16947(stack, 1);

        distInfo = new int[n + 1];
        visit = new boolean[n + 1];
        for (int i = 1; i < n + 1; i++) {
            if (isCycle[i]) {
                calculateDistance(i);
                break;
            }
        }

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

    private static void calculateDistance(int currentStation) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(currentStation);

        while (!queue.isEmpty()) {
            currentStation = queue.remove();
            for (Integer nextStation : info.get(currentStation)) {
                if (!visit[nextStation]) {
                    visit[nextStation] = true;
                    if (!isCycle[nextStation]) {
                        distInfo[nextStation] = distInfo[currentStation] + 1;
                    }
                    queue.add(nextStation);
                }
            }
        }
    }

    private static void findCycle16947(Stack<Integer> stack, int currentStation) {
        for (Integer nextStation : info.get(currentStation)) {
            // toDo : calculate result;
            if (visit[nextStation] && Math.abs(distInfo[nextStation] - distInfo[currentStation]) >= 2) {
                int endCycle = nextStation;
                int endIndex = stack.size() - 1;
                isCycle[endCycle] = true;
                while (stack.contains(endCycle) && stack.get(endIndex) != endCycle) {
                    isCycle[stack.get(endIndex)] = true;
                    endIndex--;
                }
            }

            if (!visit[nextStation]) {
                distInfo[nextStation] = distInfo[currentStation] + 1;
                visit[nextStation] = true;
                stack.add(nextStation);
                findCycle16947(stack, nextStation);
                stack.pop();
            }
        }
    }
}