[JAVA] 백준 16964번 : DFS 스페셜 저지 ( 초급 2-47 ) - hard

문제

BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.

정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.

1 2 3 4 5 6 7 8 9 10 11 12

void dfs(int x) {     if (check[x] == true) {         return;     }     check[x] = true;     // x를 방문     for (int y : x와 인접한 정점) {         if (check[y] == false) {             dfs(y);         }     } }

이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다. DFS 방문 순서는 dfs함수에서 // x를 방문 이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.

트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구해보자.

입력

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

출력

입력으로 주어진 DFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.

 

문제 풀이 

bfs 스페셜 저지 문제를 푼 사람들이라면 한 결 쉽게 해결할 수 있는 문제이다.

dfs 알고리즘은 아래와 같이 작동한다.

출처   https://developer-mac.tistory.com/64

 

dfs에 알맞는 방문 순서를 갖추고 있는지를 확인하는 문제이기 때문에

1 -> 2 로 시작하는 것과

1 -> 5

1 -> 9

로 시작하는 3가지 유형 모두를 옳은 것으로 판단할 수 있어야 한다.

 

bfs 스페셜 저지와 동일하게 parent - child 정보를 가진 어레이를 이용하여 문제를 해결하였다.

bfs 스페셜 저지를 먼저 풀어보길 바란다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class baekjoon16964 {
    private static boolean[] visit;
    private static int n;
    private static int[] expect;
    private static ArrayList<ArrayList<Integer>> info;
    private static int[] parent;

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

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

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

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            info.get(from).add(to);
            info.get(to).add(from);
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            expect[i] = Integer.parseInt(st.nextToken());
        }

        dfs16967(1, 0);
        System.out.println(1);
    }

    private static void dfs16967(int current, int index) {
        visit[current] = true;

        // 현재 값 뒤에 나올 수 있는 값들에 대한 정보를 저장.
        int count = 0;
        for (int nextCandidate : info.get(current)) {
            if (!visit[nextCandidate]) {
                visit[nextCandidate] = true;
                parent[nextCandidate] = current;
                count++;
            }
        }

        index++;
        for (int i = 0; i < count; i++) {
            int next = expect[index];
            if (parent[next] != current) {
                System.out.println(0);
                System.exit(0);
            }
            dfs16967(next, index);
        }
    }
}