[JAVA] 백준 16940번: BFS 스페셜 저지 ( 초급 2-46 ) - fail

문제

BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.

정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, BFS 알고리즘은 다음과 같은 형태로 이루어져 있다.

1. 큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다.
2. 큐가 비어 있지 않은 동안 다음을 반복한다.
   1. 큐에 들어있는 첫 정점을 큐에서 꺼낸다. 이 정점을 x라고 하자.
   2. x와 연결되어 있으면, 아직 방문하지 않은 정점 y를 모두 큐에 넣는다. 모든 y를 방문했다고 처리한다.

2-2 단계에서 방문하지 않은 정점을 방문하는 순서는 중요하지 않다. 따라서, BFS의 결과는 여러가지가 나올 수 있다.

트리가 주어졌을 때, 올바른 BFS 방문 순서인지 구해보자.

입력

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 BFS 방문 순서가 주어진다. BFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

출력

입력으로 주어진 BFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.

 

문제 풀이

bfs 알고리즘은 아래와 같다.

출처   https://developer-mac.tistory.com/64

위 예시와 같은 문제를 푼다면

1 -> 2 -> 3 -> 4  

1 -> 2 -> 4 -> 3,

1 -> 3 -> 2 -> 4

1 -> 3 -> 4 -> 2

1 -> 4 -> 2 -> 3

1 -> 4 -> 3 -> 2

순서로 시작하는 모든 것들을 정답으로 판단할 수 있어야 한다.

 

문제에서 입력으로 주는 값을 살펴보면 마지막 줄에 BFS 방문 순서가 주어진다.

예를 들어 아래와 같이 문제가 나왔다고 가정해보자

1 2 4 3 5 8 6 7 9 10

문제를 끊어서 볼 필요가 있다.

 

[1] [2 4 3] [5] [8] [6 7] [9] [10]

2, 4, 3은 1에서 파생된 것이고

5는 2에서 파생된 것

8은 4에서 파생된 것

6, 7은 3에서 파생된 것 이라는 것을 우리는 알 수 있다.

이를 기반으로 하여 코드를 작성해보자

 

누구에게서 파생되었는가? parent - child 정보를 저장하는 단계

우선 문제에서 제시된 것 과 같이 항상 1로 시작하기 때문에 큐에 1이라는 값을 넣어준다.[1]1 다음에 올 수 있는 숫자는 [2 3 4] 이다.3개의 값이 올 수 있다, [2, 3, 4]의 값들은 1을 부모로 가지고 있다.parent 어레이에 해당 정보를 저장하자.

for (Integer nextBfsNumber : info.get(currentBfsNumber)) {
    if (!visit[nextBfsNumber]) {
        visit[nextBfsNumber] = true;
        parent[nextBfsNumber] = currentBfsNumber;
        count++;
    }
}

 

parent - child 정보와 문제에서 주어진 입력값과 비교해보는 단계

입력값에서 주어진 값들과 비교해 보자1 다음에는 [2, 4, 3] 이라는 3개의 숫자가 나타난다.2, 4, 3이 1을 부모로 가지고 있는지를  parent 어레이를 이용해 검증해 본다. (parent 어레이를 이용하지 않고, info 리스트를 사용한다면 시간초과가 발생할 것이다.)만약 1을 부모로 가지고 있지 않다면 0을 출력하고 종료한다.

for (int i = 0; i < count; i++) {
    int expectBfsNumber = expect[checkIndex];
    if (parent[expectBfsNumber] != currentBfsNumber) {
        System.out.println(0);
        System.exit(0);
    }
    queue.add(expectBfsNumber);
    checkIndex++;
}

 

전체 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baekjoon16940_2 {
    private static boolean[] visit;
    private static int[] expect;
    private static ArrayList<ArrayList<Integer>> info;
    private static int n;
    private static int[] parent;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        info = new ArrayList<>();
        visit = new boolean[n + 1];
        expect = new int[n];
        parent = new int[n + 1];

        for (int i = 0; i < n + 1; i++) {
            info.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            info.get(from).add(to);
            info.get(to).add(from);
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            expect[i] = Integer.parseInt(st.nextToken());
        }

        bfs16940();
    }

    private static void bfs16940() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visit[1] = true;

        if (expect[0] != 1) {
            System.out.println(0);
            System.exit(0);
        }
        int checkIndex = 1;

        while (!queue.isEmpty()) {
            int currentBfsNumber = queue.remove();

            int count = 0;
            for (Integer nextBfsNumber : info.get(currentBfsNumber)) {
                if (!visit[nextBfsNumber]) {
                    visit[nextBfsNumber] = true;
                    parent[nextBfsNumber] = currentBfsNumber;
                    count++;
                }
            }

            for (int i = 0; i < count; i++) {
                int expectBfsNumber = expect[checkIndex];
                if (parent[expectBfsNumber] != currentBfsNumber) {
                    System.out.println(0);
                    System.exit(0);
                }
                queue.add(expectBfsNumber);
                checkIndex++;
            }

        }
        System.out.println(1);
    }
}