[BaekJoon] 16940 BFS 스페셜 저지 (Java)

1.  문제 링크

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

2.  문제

요약

• 정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, BFS 알고리즘은 다음과 같은 형태로 이루어집니다.
  1. 큐에 시작 정점을 넣습니다. 이 문제에서 시작 정점은 1입니다. 1을 방문했다고 처리합니다.
  2. 큐가 비어 있지 않은 동안 다음을 반복합니다.
     1. 큐에 들어있는 첫 정점을 큐에서 꺼냅니다. 이 정점을 x라 합니다.
     2. x와 연결되어 있으면, 아직 방문하지 않은 정점 y를 모두 큐에 넣습니다. 모든 y를 방문했다고 처리합니다.
• 2-2 단계에서 방문하지 않은 정점을 방문하는 순서는 중요하지 않습니다. 따라서, BFS의 결과는 여러가지가 나올 수 있습니다.
• 트리가 주어졌을 때, 올바른 BFS 방문 순서인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 100,000보다 작거나 같은 정점의 수 N이 주어지고 두 번째 줄부터 N - 1개의 줄에 트리의 간선 정보가 주어집니다. 마지막 줄에는 BFS 방문 순서가 주어집니다. BFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장합니다.
• 출력: 첫 번째 줄에 주어진 BFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static HashMap<Integer, ArrayList<Integer>> map;
    static int[] bfsOrder;

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

        N = scanner.nextInt();
        map = new HashMap<>();
        bfsOrder = new int[N];
        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 node = 0; node < N; node++) bfsOrder[node] = scanner.nextInt();
    }

    static void solution() {
        System.out.println(bfs(bfsOrder[0]) ? 1 : 0);
    }

    static boolean bfs(int startNode) {
        if(startNode != 1) return false;

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        HashSet<Integer> remain = new HashSet<>();

        queue.offer(startNode);
        visited[startNode] = true;

        int index = 1;
        while(!queue.isEmpty()) {
            int cur = queue.poll();

            for(int next : map.get(cur)) {
                if(!visited[next]) {
                    visited[next] = true;
                    remain.add(next);
                }
            }

            int size = remain.size();
            for(int idx = 0; idx < size; idx++) {
                if(remain.remove(bfsOrder[index])) queue.offer(bfsOrder[index++]);
                else return false;
            }
        }

        return true;
    }

    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이기 때문에 주어진 BFS 방문 순서에서 첫 번째 노드가 1이 아니라면 잘못된 BFS 방문 순서이므로 0을 출력합니다.
• 그렇지 않다면 BFS를 통해 주어진 BFS 방문 순서가 올바른지 확인합니다.
  • 각 노드에 대한 방문 체크를 위해 visited 배열을 생성하고, 방문한 배열에 인접한 노드들을 저장할 remain이라는 HashSet을 생성합니다.
  • 첫 번째 노드인 1에 대해 방문 체크를 하고 BFS 탐색을 위해 Queue에 담습니다.
  • Queue가 빌 때까지 BFS를 통해 각 노드들을 탐색합니다.
    • Queue에서 탐색할 노드를 뽑고 인접한 노드들 중 아직 방문하지 않은 노드들을 방문 체크하고 remain에 담습니다.
    • 주어진 BFS 방문 순서에서 다음에 체크해야 할 노드의 인덱스를 index라고 할 때, index번째에 있는 노드가 remain 내에 있다면 BFS 순서상 맞는 순서이므로 queue에 해당 노드를 넣어 다음 탐색에 이용하고 remain에서는 사용되었기 때문에 제거합니다.
    • 만약 index번째에 있는 노드가 remain에 없다면 잘못된 BFS 방문 순서이기 때문에 바로 false를 반환하여 0을 출력하도록 합니다.
  • 만약 Queue가 빌 때까지 false를 반환하지 않았다면 모든 방문 순서에 대해 올바르게 방문했다는 의미가 되기 때문에 true를 반환하여 1을 출력하도록 합니다.