알고리즘 풀이 - 백준 16940(BFS 스페셜 저지, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

주어진 순서가 BFS로 탐색 가능한 순서인지 알아보는 문제

 

 

2. 풀이

 

주어진 순서가 BFS로 탐색 가능한 경우의 수인지 판단하는 방법은 2가지가 있다.

① 현재 탐색 중인 정점에 연결된 정점의 부모 정점을 현재 정점으로 두고 다음 탐색할 정점의 부모 정점이 현재 탐색 중인 정점인 경우에만 가능한 경우라고 판정

② 주어진 순서를 기반으로 그래프에 정점을 저장 후, BFS 탐색 시, 같은 결과가 나오는 경우에만 가능한 경우로 판정

 

①의 경우는 아래의 그림을 통해 이해해보자.

 

위 그림을 통해 이해할 수 있는 정보는 다음과 같다. 시작이 1번 정점으로 문제에 주어졌으니 1부터 탐색을 수행한다.

현재 탐색 중인 정점 : 1
다음 탐색 대상 정점 : 2, 5
현재 주어진 순서 : 1 - 3 - 2 - 5 - 4

 

이 때, 2번, 5번 정점의 부모 정점을 1번 정점이라고 저장하면 전체 부모 정점을 저장하는 배열을 parent배열이라고 할 때 현재 저장된 값은 다음과 같을 것이다.(index를 1부터 시작한다고 가정)

parent[] = {0, 0, 1, 0, 0, 1} ▶ 즉, 2, 5번 정점의 부모가 1로 저장되어 있고 나머지 정점들은 정해지지 않은 상태가 된다.

 

이 때, 주어진 순서가 위와 같다면, 그 순서대로 탐색을 수행 시, 1 다음에 3이 되는데, 3은 부모 정점이 0으로 아직 정해지지 않았으므로 BFS로 탐색이 불가한 경우가 되는 것이다!

위 과정을 이용하여 코드로 구현할 수 있다. 그 내용은 아래에서 참고

 

 

②의 경우는 다음과 같다.

BFS는 기본적으로 연결된 정점들의 순서에 따라 탐색 결과가 달라진다. 예를 들면, 1번 정점을 탐색 후 2, 3번 정점을 탐색하는 BFS가 있다고 가정하자.

이 때, 1번 정점과 연결된 정점을 코드상으로 2, 3번 순서대로 저장하였다면 1 - 2 - 3이 되고, 3, 2번 순서대로 저장하였다면 1 - 3 - 2의 순서가 되기 때문이다.

 

그러므로, 주어진 순서에 기반하여 현재 그래프의 정점들을 정렬한 뒤, 1번 부터 단순히 BFS 탐색을 수행하여 그 결과가 주어진 순서와 동일하지 않다면 불가능한 경우가 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

①의 방법을 이용한 코드

import java.io.*;
import java.util.*;

public class Main{
    static int n;
    static ArrayList<Integer>[] graph;
    static int[] order;   // 주어진 순서 값을 저장하는 배열
    static int[] parent;  // 각 정점의 이전에 방문되는 부모 정정 저장 배열
    static boolean[] visited; // 각 정점의 방문 완료 여부 저장 배열
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        // ************** 그래프 초기화 ******************
        graph = new ArrayList[n+1];
        for(int i=1; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        StringTokenizer st = null;
        for(int i=1; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            graph[u].add(v);
            graph[v].add(u);
        }
        // ************* 여기까지 그래프 생성 완료 ****************
        
        
        
        // ************* 주어진 탐색 순서를 저장 *********************
        order = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i <= n; i++){
            order[i] = Integer.parseInt(st.nextToken());
        }
        // ************* 주어진 탐색 순서 저장 완료 ******************
        
        
        
        // ************* BFS 탐색 시 사용할 큐 생성, 부모 정점 저장 및 방문 여부 저장 배열 생성 ****
        Queue<Integer> q = new LinkedList<>();
        parent = new int[n+1];
        visited = new boolean[n+1];
        
        q.offer(1);
        visited[1] = true;  // 1번 정점에서 시작하여 방문 완료 처리
        // ************* 큐, 배열 생성 완료 *********************
        
        
        
        // ************* BFS 탐색 시작하여 순서 알맞은지 보는 코드 *****************
        int idx = 2;
        
        // order의 1부터 n까지 모두 살펴야 한다.
        for(int i=1; i <= n; i++){
            // 다 살펴보지 않았는데 큐가 비었다면 불가능한 방법이다.
            if(q.isEmpty()){
                System.out.println(0);
                System.exit(0);
            }
            
            // 큐에서 뽑은 값이 현재 order에 맞지 않으면 불가한 방법이다.
            int c = q.poll();
            if(c != order[i]) {
                System.out.println(0);
                System.exit(0);
            }
            
            // 현재 정점과 인접한 정점을 Child라고 하고 그 수를 센 다음, 부모 정점으로 저장
            int cnt = 0;  // child의 개수를 저장하는 변수
            for(int child : graph[c]){
                if(!visited[child]){
                    parent[child] = c;
                    cnt++;
                }
            }
            
            // 현재 index부터 자식의 개수만큼 index를 검사하여 다음 탐색할 정점을 찾는다.
            for(int j=0; j < cnt; j++){
            
                // n을 넘어가거나 부모가 현재 정점이 아닌데 다음 순서에 있다면 불가한 경우
                if(j+idx > n || parent[order[j+idx]] != c){
                    System.out.println(0);
                    System.exit(0);
                }
                // 큐에 추가하고 방문 완료 처리한다.
                q.offer(order[j+idx]);
                visited[order[j+idx]] = true;
            }
            
            // 자식들 추가된 수만큼 더해 준다.
            idx += cnt;
        }
        
        System.out.println(1);
        br.close();
    }
}

 

 

②의 방법을 이용한 코드(순서를 지정하여 BFS 탐색을 수행하는 방법)

import java.io.*;
import java.util.*;

public class Main{
    static int n;
    static ArrayList<Integer>[] graph;
    static int[] num;     // 숫자값을 저장
    static int[] order;   // 주어진 순서 값을 저장하는 배열
    static int[] parent;  // 각 정점의 이전에 방문되는 부모 정정 저장 배열
    static boolean[] visited; // 각 정점의 방문 완료 여부 저장 배열
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        // ************** 그래프 초기화 ******************
        graph = new ArrayList[n+1];
        for(int i=1; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        StringTokenizer st = null;
        for(int i=1; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            graph[u].add(v);
            graph[v].add(u);
        }
        // ************* 여기까지 그래프 생성 완료 ****************
        
        
        // ************* 주어진 탐색 순서를 저장 *********************
        num = new int[n+1];
        order = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i <= n; i++){
            num[i] = Integer.parseInt(st.nextToken());
            order[num[i]] = i;  // 각 숫자가 나올 위치를 저장
        }
        // ************* 주어진 탐색 순서 저장 완료 ******************
        
        
        // ********** 그래프 내 저장된 정점을 순서 기반 정렬 **********
        for(int i=1; i <= n; i++){
            Collections.sort(graph[i], new Comparator<Integer>(){
                public int compare(Integer u, Integer v){
                    if(order[u] < order[v]){
                        return -1;
                    } else if(order[u] == order[v]){
                        return 0;
                    } else {
                        return 1;
                    }
                }
            });
        }
        // ************************* 정렬 완료 **********************
        
        
        // ************* BFS 탐색 시작하여 순서 알맞은지 보는 코드 *****************
        Queue<Integer> q = new LinkedList<>();
        visited = new boolean[n+1];
        
        int idx = 0;
        q.offer(1);
        while(!q.isEmpty()){
            int u = q.poll();
            idx++;
            
            // 현재 탐색하고자 하는 정점이 순서에 맞지 않는다면 0 출력하고 끝낸다.
            if(num[idx] != u){
                System.out.println(0);
                System.exit(0);
            }
            
            visited[u] = true;
            for(int v : graph[u]){
                if(!visited[v]){
                    q.offer(v);
                }
            }
        }
        
        // 모두 탐색 완료 시, 1을 탐색한다.
        System.out.println(1);
        br.close();
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.