[백준] 16940번 : DFS 스페셜 저지 - JAVA [자바]

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

dfs 알고리즘 문제이다.

BFS 스페셜 저지 문제를 풀고 나면 이해하기가 쉽다.

같은 부모 아래에 있는 자식 노드의 순서는 바뀔 수 있다.

public class bj16964 {

    public static int N;
    public static boolean[] visited;
    public static boolean answer = true;
    public static int[] inputAnswer;
    public static int childIndex = 1;
    public static Queue<Integer> queue = new LinkedList<>();
    public static ArrayList<ArrayList<Integer>> edgeList;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        visited = new boolean[N + 1];
        inputAnswer = new int[N];

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

        for (int i = 0; i < N - 1; i++) {
            String line1 = br.readLine();
            String[] split1 = line1.split(" ");
            int from = Integer.parseInt(split1[0]);
            int to = Integer.parseInt(split1[1]);
            edgeList.get(from).add(to);
            edgeList.get(to).add(from);
        }

        String line = br.readLine();
        String[] split = line.split(" ");
        for (int i = 0; i < N; i++) {
            inputAnswer[i] = Integer.parseInt(split[i]);
        }

        checkDFS(1);

        if (inputAnswer[0] != 1) answer = false;

        if (answer) sb.append(1);
        else sb.append(0);

        bw.write(sb + "");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void checkDFS(int start) {
        if (visited[start]) return;

        // start 정점 방문
        visited[start] = true;
        HashSet<Integer> set = new HashSet<>();
        for (int to : edgeList.get(start)) {
            // 자식 노드면
            if (!visited[to]) set.add(to);
        }

        if (set.isEmpty()) return;

        if (set.contains(inputAnswer[childIndex])) {
            checkDFS(inputAnswer[childIndex++]);
        } else answer = false;
    }
}