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

문제 바로가기 : https://www.acmicpc.net/problem/16947

메모리 : 230948KB

시간 : 872ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static List<List<Integer>> list;
    static int N;
    static boolean[] check;

    static class Node {
        int num, cnt;

        Node(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
        StringTokenizer st;
        check = new boolean[N + 1];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
        }
        // 사이클인지
        for (int i = 1; i <= N; i++) {
            if (isCycle(i, i, i)) {
                break;
            }
        }
        int[] ans = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            // 사이클이면 0 사이클아니면 사이클찾아가기
            if (!check[i]) {
                ans[i] = findCycle(i);
            }
            sb.append(ans[i]).append(" ");
        }
        System.out.print(sb);
    }

    private static int findCycle(int now) {
        boolean[] visit = new boolean[N + 1];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(now, 0));
        visit[now] = true;
        while (!q.isEmpty()) {
            Node n = q.poll();
            if (check[n.num]) {
                return n.cnt;
            }
            for (int i = 0; i < list.get(n.num).size(); i++) {
                if (!visit[list.get(n.num).get(i)]) {
                    visit[list.get(n.num).get(i)] = true;
                    q.add(new Node(list.get(n.num).get(i), n.cnt + 1));
                }
            }
        }
        return 0;
    }

    private static boolean isCycle(int start, int now, int before) {
        check[now] = true;
        for (int i = 0; i < list.get(now).size(); i++) {
            if (!check[list.get(now).get(i)]) {
                if (isCycle(start, list.get(now).get(i), now))
                    return true;
            } else if (before != list.get(now).get(i) && start == list.get(now).get(i)) {
                return true;
            }
        }
        check[now] = false;
        return false;
    }
}

풀이

문제 이해하기가 참 어려웠다..ㅋㅋ 사이클에 속하는 노드는 모두 하나로 보면 되고 루트노드가 된다. 사이클에서 삐져나온 간선에서 사이클까지의 거리를 구하면 되는 문제였다.

깊게 생각안하고 풀었더니.. 시간이 오래걸렸다ㅋㅋ

일단 사이클을 구한다. 사이클은 dfs를 이용해 시작점과 끝점이 일치하면 사이클로 보고 배열에 기록해놓는다. 그다음 간선에서 사이클이 true인 노드까지 bfs로 개수를 세주면 된다.