BOJ (Java) 16940번: BFS 스페셜 저지

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

---

풀이

문제의 이름처럼 BFS 탐색을 하며 확인했다.

입력으로 주어진 BFS 방문 순서에 따라 우선순위를 부여해 BFS 시에 참고했다.

우선순위 큐를 사용, 현재 단계에 탐색 가능한 모든 노드들을 저장하되 주어진 방문 순서대로 정렬했다.

 

방문 순서가 올바른지 판단하는 데에는 list를 사용했다.

각 단계마다 list에 값을 넣어두고, 이 또한 주어진 순서에 따라 정렬했다.

이 경우 입력받은 순서가 올바르다면 list에 있는 값과 입력받은 순서가 일치해야 한다.

따라서 일치하지 않는 경우는 올바르지 않다고 판단했다.

 

 

입력 받은 순서를 저장해두고, 이 값으로 가지고 온다는 건 생각하지 못 했다...
작은 디테일 하나를 생각하는 연습이 더 필요한 것 같다ㅠ

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    private static int N;
    private static int[] orders;
    private static int[] priority;
    private static boolean[] visited;
    private static HashSet<Integer>[] map;
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());

        orders = new int[N];
        priority = new int[N + 1];
        visited = new boolean[N + 1];
        map = new HashSet[N + 1];
        for (int i = 1; i <= N; i++) {
            map[i] = new HashSet<>();
        }

        String[] inputs;
        for (int i = 0; i < N - 1; i++) {
            inputs = bf.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);
            map[a].add(b);
            map[b].add(a);
        }

        inputs = bf.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            orders[i] = Integer.parseInt(inputs[i]);
            
            // 입력된 순서에 따라 우선순위 부여
            priority[orders[i]] = i;
        }

        // bfs 탐색 시 가능한 순서인지 확인
        if (checkPossibility()) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    private static boolean checkPossibility() {
        int orderIdx = 1;
        
        // 단계별 옳은 순서인지 확인용
        List<Integer> checkOrder = new ArrayList<>();
        
        // BFS 탐색용, 주어진 탐색 순서에 따라 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a, b) -> Integer.compare(priority[a], priority[b]));
        
        pq.add(1);
        while (!pq.isEmpty()) {
            checkOrder.clear();
            int now = pq.poll();

            visited[now] = true;
            for (int next : map[now]) {
                if (visited[next]) continue;
                pq.add(next);
                visited[next] = true;
                checkOrder.add(next); // 확인용
            }

            // 현재 레벨의 모든 노드들을 넣고, 입력순서대로 정렬
            checkOrder.sort((a, b) -> Integer.compare(priority[a], priority[b]));
            for (int seq : checkOrder) {
                
                // 들어온 순서대로 정렬했음에도 그 값과 비교했을 때 값이 다르다면 -> 틀린 순서
                if (orders[orderIdx] != seq) {
                    return false;
                }
                orderIdx++;
            }
        }
        return true;
    }
}