[JAVA] 백준 16947 - 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

 

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

public class Main{
    static int n;
    static int[] distance;
    static boolean[] visited, cycle;
    static List<Integer> list[];
    static Queue<Integer> q = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        list = new ArrayList[n + 1];
        distance = new int[n+1];
        cycle =new boolean[n+1];

        StringBuilder sb = new StringBuilder();

        for(int i=1; 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);
        }
        for(int i=1; i<=n; i++){ // 모든 노드들을 시작점으로 dfs 탐색
            visited = new boolean[n+1];
            findCycle(i, i, 1);
        }
        for(int i=1; i<=n; i++){
            if(cycle[i]) q.add(i); // 사이클에 속한 노드들만 큐에 넣음
            else distance[i] = -1; // 나머지 노드들의 거리는 -1로 초기화
        }

        bfs();

        for(int i=1; i<=n; i++){
            sb.append(distance[i]).append(" ");
        }
        System.out.println(sb);
    }
    static void bfs(){ // 최소 거리이므로 bfs
        // 사이클에 속한 노드들로부터 인접한 노드들을 탐색해 나가며 거리를 1씩 증가시킨다.
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int next : list[cur]){
                if(distance[next] == -1){ // 사이클에 속하지 않은 노드이고 첫 방문이면
                    distance[next] = distance[cur]+1;
                    q.add(next);
                }
            }
        }
    }


     static void findCycle(int start, int cur, int cnt){ // 노드 수가 n개고 간선의 수도 n개 이므로 사이클은 무조건 하나다.
        visited[cur] = true;
        for(int next: list[cur]){
            if(next == start && cnt >= 3) { // 시작점과 같은 노드이고 cnt가 3이상이라면 사이클 (2라면 직전 노드로 다시 가는 것일 수 있음)
                cycle[next] = true;
                return;
            }
            else if(!visited[next]) findCycle(start, next, cnt+1);
        }
    }
}