[JAVA] 백준 16964 - DFS 스페셜 저지

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

16964번: DFS 스페셜 저지

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

public class Main {
    static int n;
    static boolean[] visit;
    static ArrayList<ArrayList<Integer>> list;
    static int[] expect;
    static int[] parent;


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

        n = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        visit = new boolean[n + 1];
        expect = new int[n + 1];
        parent = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            StringTokenizer 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);
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            expect[i] = Integer.parseInt(st.nextToken());
        }

        if (expect[1] != 1) { // 입력 값의 첫번째 값이 1이 아니면
            System.out.println(0);
            System.exit(0);
        }

        dfs(1, 2);
        System.out.println(1);

    }

    public static void dfs(int cur, int idx) {
        visit[cur] = true;

        int cnt = 0;
        for (int next : list.get(cur)) {
            if (!visit[next]) {
                visit[next] = true;
                parent[next] = cur; // 부모 저장
                cnt++;
            }
        }
        if (cnt == 0) return; // 자식이 없으면 리턴

        int expectNum = expect[idx];
        if (parent[expectNum] != cur) { // 부모가 맞지 않다면
            System.out.println(0);
            System.exit(0);
        }
        dfs(expectNum, idx + 1);
    }

}

 

 

코드는 정답으로 통과됐는데 이상한 점이 하나 있다.

4
1 2
1 3
2 4
1 3 4 2

 

이렇게 입력받았을 경우 DFS 탐색이 아니여서 정답은 0이 되어야 하는데, 1이 나온다는 점이다.

다른 구글링한 코드들로 해봐도 같은 결과였다.

문제 오류같아서 일단 문의를 드렸다.