[백준]16964번. DFS 스페셜 저지(JAVA)

문제

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

---

풀이(30분)

import java.io.*;
import java.util.*;

public class Main {

    // 인접 리스트 (그래프)
    static List<ArrayList<Integer>> list = new ArrayList<>();
    static boolean[] visited; // 방문 여부
    static int[] next;        // 주어진 방문 순서
    static boolean flag;      // 순서가 유효한지 판별
    static int n, idx;        // 정점 수, 현재 순서 인덱스

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

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

        // 인접 리스트 초기화
        for(int i = 0; i <= n; ++i) list.add(new ArrayList<>());

        visited = new boolean[n + 1];
        next = new int[n];
        flag = true;
        idx = 1; // 첫 번째는 1로 고정, 다음 인덱스부터 비교

        // 간선 정보 입력
        for(int i = 0; i < n - 1 ; ++i) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            list.get(from).add(to);
            list.get(to).add(from);
        }

        // 방문 순서 입력
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; ++i) next[i] = Integer.parseInt(st.nextToken());

        // 시작 노드가 1이 아니면 잘못된 순서
        if(next[0] != 1) {
            System.out.println(0);
            return;
        }

        // DFS 시작
        dfs(1);

        // 결과 출력
        System.out.println(flag ? 1 : 0);
    }

    private static void dfs(int x) {
        if(visited[x]) return;

        visited[x] = true; // 현재 노드 방문 처리

        // 현재 노드에서 방문 가능한 자식 노드 수집
        HashSet<Integer> set = new HashSet<>();
        for(int next : list.get(x)) {
            if(visited[next]) continue;
            set.add(next);
        }

        // 더 방문할 자식 노드가 없으면 리턴
        if(set.size() == 0) return;

        // 다음 방문 노드가 자식 중 하나인지 확인
        if(set.contains(next[idx])) {
            dfs(next[idx++]); // 맞으면 계속 탐색
        } else {
            flag = false;     // 순서가 잘못됨
        }
    }
}

---

문제 풀이 전략

 

단순한 dfs와 유사하지만 가장 큰 차이점이라면 어떤 자식을 우선 방문할지 모른다는 것이다.

그렇기에 리스트를 다시 집합에 넣고, 문제에서 지정해 준 방문 순서에 맞게 방문 처리를 해주며 진행한다.

 

이 과정에서 어긋난다면 바로 flag = false로 최종 결과를 출력해 주면 된다.