[백준] 16940번 BFS 스페셜 저지 문제 풀어보기 (Collections.sort()) : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/16940

2) 문제

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

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

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

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

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

3) 입력

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

4) 출력

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

더 자세한 문제의 조건을 보려면 위의 링크에 방문해보자.

2. 풀이

이 문제는 BFS의 가능한 경우의 수가 여러 개 있다는 아이디어에서 출발한다.

BFS는 한 번만 모든 경우를 다 순회하면 되기 때문에 가능한 답이 여러개이다.

문제에서 주어진 배열을 보고 이 경우가 가능한 경우인지를 판단하면 된다.

먼저 인접리스트를 사용하여서 이 문제를 풀 것인데,

예를 들어 1과 인접해있는 숫자가 4와 6이라고 해보자.

그런데 문제에서 4보다 6이 마지막줄에 먼저 나왔다면 1에 해당하는 ArrayList의 정렬을 6, 4로 해주는 것이다. 나는 ord 라는 배열을 만들어서 입력 마지막 줄의 각 숫자에 대한 순서를 저장했다. 즉 ord[a]가 ord[b]보다 작다면 각 노드의 ArrayList에서 a를 b보다 앞으로 정렬하는 것이다. 이는 Collections.sort에서 public int compare(Integer a, Integer b)를 사용해주면 된다.

sorting하는 코드부터 보면,

  
      for(int i=0; i<n; i++){
          Collections.sort(arr[i], new Comparator<Integer>(){
             public int compare(Integer a, Integer b){
                 if (ord[a]<ord[b]){
                     return -1;
                 }
                 else return 1;
             } 
          });
      }

위와 같이 구할 수 있다.

이렇게 인접리스트를 모두 다 정렬하면 이제 1에서 시작하는 것은 동일하기 때문에 인접리스트로 BFS를 구한 답과 문제에서 주어진 답을 일일히 비교하면 된다.

예전 BFS문제에서는 가능한 BFS의 순서를 출력하는 문제였기 때문에 단순히 queue 하나가 필요하고 그것을 remove할 때마다 출력만 해주면 되었다. 하지만 이 문제에서는 배열 두개를 비교해야 하기 때문에 실제로 하나씩 pop할 것을 담는 ArrayList

ArrayList<Integer> comparedList=new ArrayList<>();

을 하나 더 만들었다. 이제 queue에서 pop한 것을 하나씩 comparedList에서 담으면서 문제에서 주어진 배열과 같은지만 확인하면 된다.

문제의 입력을 받는 배열은 내 코드에서는 inp[] 이다. (input을 줄여쓴것)

전체 코드를 살펴보면

import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
         int n=sc.nextInt();
        ArrayList<Integer> arr[]=new ArrayList[n];
        for(int i=0; i<n; i++){
            arr[i]=new ArrayList<>();
        }
        for(int i=0; i<n-1; i++){
            int from=sc.nextInt()-1;
            int to=sc.nextInt()-1;
            arr[from].add(to);
            arr[to].add(from);
        }
        
        int inp[]=new int[n];
        int ord[]=new int[n];
        for(int i=0; i<n; i++){
            inp[i]=sc.nextInt()-1;
            ord[inp[i]]=i;
        }
       
      for(int i=0; i<n; i++){
          Collections.sort(arr[i], new Comparator<Integer>(){
             public int compare(Integer a, Integer b){
                 if (ord[a]<ord[b]){
                     return -1;
                 }
                 else return 1;
             } 
          });
      }
        boolean check[]=new boolean[n];
        Queue<Integer> q= new LinkedList<>();
        ArrayList<Integer> comparedList=new ArrayList<>();
        q.add(0);
        check[0]=true;
        while(!q.isEmpty()){
            int x=q.remove();
            comparedList.add(x);
            for(int y: arr[x]){
                if (!check[y]){
                    q.add(y);
                    check[y]=true;
                }
            }
        }
        boolean isTrue=true;
        for(int i=0; i<n; i++){
            if (comparedList.get(i)!=inp[i]){
                isTrue=false;
                break;
            }
        }
        if (isTrue){
            System.out.println(1);
        }
        else{
            System.out.println(0);
        }
    }
}

위와 같이 구할 수 있다.

즉 이 문제는 BFS가 여러가지 순서로 나올 수 있지만 인접리스트를 나타내는 ArrayList를 문제의 order에 따라서 정렬하고 난 후에는 가능한 경우가 1가지라는 것을 고려하여 코드를 작성할 수 있다.