[BaekJoon] 16964 DFS 스페셜 저지 (Java)

1.  문제 링크

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

2.  문제

요약

• 정답이 여러가지인 경우에는 스페셜 저지를 사용하는데 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식입니다.
• 정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매개져있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있습니다.

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 방문 순서인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 100,000보다 작거나 같은 정점의 수 N이 주어지고 두 번째 줄부터 N - 1개의 줄에 트리의 간선 정보가 주어집니다. 마지막 줄에는 DFS 방문 순서가 주어집니다. DFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장합니다.
• 출력: 첫 번째 줄에 입력으로 주어진 DFS 방문 순서가 올바른 순서라면 1을, 아니라면 0을 출력합니다.

3.  소스코드

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

public class Main {
    static int N, index;
    static boolean flag;
    static HashMap<Integer, ArrayList<Integer>> map;
    static int[] dfsOrder;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        map = new HashMap<>();
        dfsOrder = new int[N + 1];
        for(int node = 1; node <= N; node++) map.put(node, new ArrayList<>());

        for(int edge = 1; edge < N; edge++) {
            int node1 = scanner.nextInt(), node2 = scanner.nextInt();

            map.get(node1).add(node2);
            map.get(node2).add(node1);
        }

        for(int order = 0; order < N; order++)
            dfsOrder[order] = scanner.nextInt();
    }

    static void solution() {
        if(dfsOrder[0] != 1) {
            System.out.println(0);
            return;
        }

        index = 1;
        flag = true;

        dfs(1, new boolean[N + 1]);
        
        if(flag) System.out.println(1);
        else System.out.println(0);
    }

    static void dfs(int node, boolean[] visited) {
        if(visited[node]) return;
        visited[node] = true;

        HashSet<Integer> set = new HashSet<>();
        for(int next : map.get(node)) {
            if(!visited[next]) set.add(next);
        }

        if(set.size() == 0) return;

        if(set.contains(dfsOrder[index])) dfs(dfsOrder[index++], visited);
        else flag = false;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 시작 정점은 1이기 때문에 주어진 DFS 방문 순서가 1이 아니라면 올바른 탐색 순서가 아니기 때문에 0을 출력합니다.
• 그렇지 않다면 아래와 같이 DFS를 진행하며 올바른 탐색 순서인지 확인합니다.
  • 시작 정점이 아닌 바로 다음 정점부터 시작합니다.
  • 만약 현재 탐색 중인 정점이 방문한 정점이라면 다음 정점을 탐색합니다.
  • 그렇지 않다면 현재 정점에 대해 방문 체크를 진행하고 현재 정점과 이어져있는 정점들을 HashSet에 담습니다.
  • 만약 이어진 정점이 없다면, 즉 HashSet의 크기가 0이라면 다음 정점을 탐색합니다.
  • 그렇지 않다면 HashSet에 현재 순서의 정점이 있는지 확인합니다.
    • 만약 존재한다면 지금까지의 주어진 DFS 방문 순서는 맞는 것이기 때문에 재귀를 통해 이후의 정점들을 탐색합니다.
    • 존재하지 않는다면 잘못된 DFS 방문 순서이므로 올바른 방문 순서인지를 나타내는 flag 변수에 false 값을 설정합니다.
• 위 DFS 탐색을 마친 후에 flag가 true라면 올바른 방문 순서이므로 1을, flag가 false라면 올바르지 않은 방문 순서이므로 0을 출력합니다.