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

요구사항

역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

 

문제 해설

최소거리를 확인하는 문제가 아니기 때문에 dfs를 이용하였다.

기존 dfs 문제와 다른점이라고 한다면, 사이클 (순환선) 에 포함되는 역을 찾아야 한다는 것이다.

아래와 같은 로직을 이용하여 문제를 풀어보았다.

1. 지나는 역을 모두 스택에 넣는다.

2. 이미 방문한 역이 면서 거리차이가 2이상일 경우, 해당역은 사이클의 시작지점이자 종결지점이다.

3. 사이클의 시작지점이 나타날 때까지 스택에서 값을 하나씩 빼고, 뺀 값은 사이클의 포함되는 것을 표시해주었다. (isCycle)

4. 마지막으로 사이클의 포함되는 지역은 0을 print 해주고 cycle에 포함되지 않는 값인 경우에는 가장 가까운 cycle과의 거리를 print해주었다.

 

 dfs에서 return을 처음 해보았는데, 어떤 지점에서 어떤 값을 return해야 하는지 많이 고민되었다.

print로 계속해서 값이 어떻게 나타나는지 확인하면서 문제를 풀어 보았는데, 주먹구구식으로 푼 느낌이 커서 다시 한번 더 풀어보아야 할 것 같다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class baekjoon16947 {
    static boolean[] visit;
    static ArrayList<Integer>[] info;
    static int[] dist;
    static boolean[] isCycle;
    static Stack<Integer> stack;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        visit = new boolean[n + 1];
        info = new ArrayList[n + 1];
        dist = new int[n + 1];
        isCycle = new boolean[n + 1];
        stack = new Stack<>();
        for (int i = 1; i <= n; i++) {
            info[i] = new ArrayList<>();
            visit[i] = true;
            isCycle[i] = false;
        }

        for (int i = 1; i < n + 1; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            info[x].add(y);
            info[y].add(x);
        }

        for (int i = 1; i < n + 1; i++) {
            if (visit[i]) {
                dfs(i, 1);
                // toDO : dfs
            }
        }
        // System.out.println(info[3]);
        // System.out.println(Arrays.toString(isCycle));
        // System.out.println(Arrays.toString(dist));

        for (int i = 1; i < n + 1; i++) {
            if (isCycle[i]) {
                System.out.print("0 ");
            } else {
                Queue<Integer> q = new LinkedList<>();
                int[] d = new int[n + 1];
                q.add(i);
                while (!q.isEmpty()) {
                    int temp = q.poll();
                    if (isCycle[temp]) {
                        System.out.print(d[temp] + " ");
                        break;
                    }
                    for (Integer target : info[temp]) {
                        if (d[target] == 0) {
                            d[target] = d[temp] + 1;
                            q.add(target);
                        }
                    }
                }
            }
        }
        System.out.println();
    }

    static int dfs(int x, int cnt) {
        stack.push(x);
        dist[x] = cnt;
        visit[x] = false;
        int res = -1;
        for (int target : info[x]) {
            // System.out.println(x);
            // System.out.println(target);

            if (visit[target]) {
                // System.out.println("go dfs");
                // System.out.println();
                res = dfs(target, cnt + 1);
            } else if (cnt - dist[target] >= 2) {
                // System.out.println("find cycle");
                // System.out.println();
                isCycle[target] = true;
                res = target;
            } else {
                // System.out.println("continue");
                // System.out.println();
                continue;
            }
            // System.out.println(stack);
            // System.out.println("sub res" + res);
            // System.out.println();
            if (res != -1) {
                while (stack.size() > 0) {
                    // System.out.println("HI");
                    int temp = stack.pop();
                    isCycle[temp] = true;
                    if (temp == res) {
                        res = -1;
                        break;
                    }
                }
            }
        }
        // System.out.println("total res" + res);
        // System.out.println();
        if (stack.size() > 0) {
            stack.pop();
        }

        return res;
    }

}