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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

16964번: DFS 스페셜 저지

---

2. 내가 푼 방법

이 문제는 제목 그대로 DFS 알고리즘을 구현해 가능한 방문 순서인지 확인하면 된다.

 

중요한 부분은 방문한 적 없는 노드인지, 자식 노드인지(=갈 수 있는 경로인지)를 확인함으로써 nextNode가 현재 노드에서 갈 수 있는 다음 노드인지 확인하는 부분이다. 자식 노드인지 확인하기 위해 처음엔 모든 간선을 저장한 list를 이용해 포함하고 있는지를 확인해 줬었는데, 이 경우 O(N) 시간복잡도로 시간초과가 발생했다. 따라서 사전에 부모 노드를 저장해줌으로써 O(1) 시간복잡도를 시간초과를 해결할 수 있었다.

 

깊이 우선 탐색은 한 방향을 우선적으로 탐색하기 때문에, 가장 마지막에 탐색된 인덱스를 반환해줌으로써 올바른 순서인지 확인할 수 있다. 또한 루트 노드일 경우에만 (자식 노드의 수)만큼 for문이 돌고, 그 외에는 (자식 노드의 수 - 1)만큼 for문이 돌아가기 때문에 주의해야 한다.

ic static void solution() {
    getParent();

    visit[1] = true;
    if (dfs(1) == N) {
        isPossible = 1;
    }
}

public static int dfs(int idx) {
    int node = arr[idx];
    int minus = (node == 1) ? 0 : 1;

    for (int i = 0; i < list[node].size() - minus; i++) {
        int nextNode = arr[idx + 1];

        if (!visit[nextNode] && parent[nextNode] == node) {
            visit[nextNode] = true;
            idx = dfs(idx + 1);

            if (idx == -1) return -1;
        }
        else return -1;
    }

    return idx;
}

public static void getParent() {
    Queue<Integer> queue = new ArrayDeque<>();

    parent[1] = 1;
    queue.add(1);

    while (!queue.isEmpty()) {
        int q = queue.poll();

        for (Integer i : list[q]) {
            if (parent[i] == 0) {
                parent[i] = q;
                queue.add(i);
            }
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B16964.java

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

class Main {
    static int N;
    static List<Integer>[] list;
    static int[] arr;
    static int[] parent;
    static boolean[] visit;
    static int isPossible;

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

    public static void solution() {
        getParent();

        visit[1] = true;
        if (dfs(1) == N) {
            isPossible = 1;
        }
    }

    public static int dfs(int idx) {
        int node = arr[idx];
        int minus = (node == 1) ? 0 : 1;

        for (int i = 0; i < list[node].size() - minus; i++) {
            int nextNode = arr[idx + 1];

            if (!visit[nextNode] && parent[nextNode] == node) {
                visit[nextNode] = true;
                idx = dfs(idx + 1);

                if (idx == -1) return -1;
            }
            else return -1;
        }

        return idx;
    }

    public static void getParent() {
        Queue<Integer> queue = new ArrayDeque<>();

        parent[1] = 1;
        queue.add(1);

        while (!queue.isEmpty()) {
            int q = queue.poll();

            for (Integer i : list[q]) {
                if (parent[i] == 0) {
                    parent[i] = q;
                    queue.add(i);
                }
            }
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(isPossible+"");

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

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        list = new ArrayList[N+1];
        arr = new int[N+1];
        parent = new int[N+1];
        visit = new boolean[N+1];

        for (int i = 1; i <= N; i++) {
            list[i] = 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[a].add(b);
            list[b].add(a);
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        br.close();
    }
}

---

4. 결과 및 회고

루트 노드가 아닐 경우에는 (자식 노드의 수 - 1)만큼 for문이 돌아간다는 걸 놓쳐서 한 번에 해결하지 못했다. BFS 스페셜 저지 풀 때도 그랬는데,, 조금 더 집중할 수 있도록 해보자.