[백준 *Java] - BFS 스페셜 저지 (16940)

BFS 스페셜 저지

16940번: BFS 스페셜 저지

 

👇 문제보기

문제 설명

BOJ 에서 정답이 여러가지인 경우에는 스페셜 저지를 사용합니다.

스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식입니다.

오늘은 스페셜 저지 코드를 하나 만들어 보려고 합니다.

 

정점의 개수가 N이고, 정점에서 1부터 N까지 번호가 매겨져 있는 양방향 그래프가 있을 때,

BFS 알고리즘은 다음과 같은 형태로 이루어져 있습니다.

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

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

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

 

입력

첫째 줄에 정점의 수 N (2 <= N <= 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다.

마지막 줄에는 BFS 방문 순서가 주어진다.

BFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

 

출력

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

👇 접근방식 (내 생각 정리)

---

문제 설명한 부분은 어느정도 일반화된 BFS 문제 풀이를 설명해주는 거 같습니다.

너비 우선 탐색을 할 때, 순서가 불규칙하지만, 순서 값을 매 번 확인해주는 방식으로 코드를 구현하게 된다면?

1과 0을 구분하고 바로 break return 으로 빠져나오는 식으로 구혈할까 합니다.

하지만 우려되는 부분은 매번 비교를 하니깐 시간복잡도 부분에서 걸리는 게 아닐까라는 걱정이 있습니다. 일단 문제를 구현하고 처음 접근했던 방식에서 문제점이 발생하면 다시 정리를 해보도록 하겠습니다.

 

---

 

틀린 코드

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 Main {
    static int N;
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    static int[] nodeOrder;
    static int check = 2;
    static boolean breakP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // 인접 리스트 선언
        for (int i = 0; i < N + 1; i++) {
            adjList.add(new ArrayList<>());
        }

        // 방문처리 선언
        visited = new boolean[N + 1];

        // 인접 리스트 초기화
        StringTokenizer st;
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            adjList.get(x).add(y);
            adjList.get(y).add(x);
        }

        // 입력 받은 순서 초기화
        nodeOrder = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            nodeOrder[i] = Integer.parseInt(st.nextToken());
        }
        if (nodeOrder[0] != 1) {
            System.out.println(0);
            return;
        }

        // bfs
        for (int i = 1; i < N; i++) {
            Queue<Integer> qu = new LinkedList<>();
            if (!visited[i]) {
                qu.offer(i);
                while (!qu.isEmpty()) {
                    int node = qu.poll();
                    for (int adjNode : adjList.get(node)) {
                        if (check <= N && !orderCheck(node)) {
                            breakP = true;
                            System.out.println(0);
                            break;
                        }

                        if (!visited[adjNode]) {
                            visited[adjNode] = true;
                            qu.offer(adjNode);
                        }
                    }
                    if (breakP) break;
                }
            }
            if (breakP) break;
        }

        if (!breakP) System.out.println(1);
    }

    private static boolean orderCheck(int node) {
        for (int adjNode : adjList.get(node)) {
            if (nodeOrder[check] == adjNode) {
                check++;
                return true;
            }
        }
        return false;
    }
}

 

테스트케이스는 맞다고 나오지만, 설계를 했을 때 제가 가정하고 짠 로직의 빈틈이 있을 거라 생각했긴 했지만 그게 뭔지 찾아봐야할 거 같습니다...

 

아래는 성공한코드 입니다.

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;

/*

* 주의할 점 *
    1. 시작 정점은 1이기 때문에 1이 아닌 다른 정점부터 시작하는 방문 순서는 올바르지 않습니다.
    2. 간선은 양방향으로 저장
    3. 같은 레벨에 있는 정점들의 순서만 중요합니다. 즉, 한 정점에서 이동하는 정점들과 다른 정점에서 이동하는 정점들의 순서가 섞이면 안 됩니다
*/

public class Main {
    static int N; 
    static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    static boolean[] visited;
    static int[] inputArr;
    static Queue<Integer> qu = new LinkedList<>();
    static StringTokenizer st;

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

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N + 1];
        inputArr = new int[N + 1];


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

        for(int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            adjList.get(x).add(y);
            adjList.get(y).add(x);
        }

        // input 데이터 저장
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i < N + 1; i++) {
            inputArr[i] = Integer.parseInt(st.nextToken());
        }

        isPossibleBfs(1);
    }

    public static void isPossibleBfs(int x) {
        // 시작이 1이 아니면 0으로 아웃
        if(inputArr[1] != 1) {
            System.out.println(0);
            return;
        }

        qu.offer(x);
        visited[x] = true;

        int index = 2;
        while(!qu.isEmpty()) {
            int cur = qu.poll();

            // 현재 노드의 자식들 방문 처리
            int count = 0;
            for(int next : adjList.get(cur)) {
                if(!visited[next]) {
                    visited[next] = true;
                    count++;
                }
            }

            for(int i = index; i < (index + count); i++) {
                // 정답이 현재 노드의 자식이 아니라면 X
                if(!visited[inputArr[i]]) {
                    System.out.println(0);
                    return;
                } else qu.offer(inputArr[i]); // 정답이 현재 노드의 자식이면 큐에 순서대로 삽입
            }
            index += count;
        }

        System.out.println(1);
    }
}