[BOJ 16940] BFS 스페셜 저지 (Java)

BOJ 16940 BFS 스페셜 저지

문제풀이

간단한 문제인줄 알고 덤볐다가 큰 코 다친 문제다.

단순하게 트리의 같은 레벨에 있는 노드끼리는 방문순서를 바꿔도 된다라고 생각하여 여러가지 구현을 해보았지만 모두 실패하였다. 문제는 바로 큐에 들어가는 순서에 따라서 다음(자식) 노드의 방문 순서가 정해진다는 것이였다.

                               1
                             /   \
                            2     3
                           / \   / \
                          4   5 6   7

위와 같은 트리가 있을 때 2와 3 그리고 4, 5, 6, 7은 각각 같은 레벨이기 때문에 순서가 바뀌어도 되는 것 같다. 1, (2, 3), (4, 5, 6, 7)

하지만 잘 생각해보면 큐의 작동 방식 때문에 2, 3의 큐에 넣는 순서에 따라서 다음 (4, 5, 6, 7)의 방문순서가 정해진다는 것을 알 수 있다.

• 2를 먼저 큐에 넣는다면 2의 자식 노드인 (4, 5)가 먼저 나와야한다.
• 3을 먼저 큐에 넣는다면 3의 자식 노드인 (6, 7)가 먼저 나와야한다.

구현코드

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

public class Main {

	static ArrayList<ArrayList<Integer>> adj;
	static Queue<Integer> q;
	static boolean[] visited;
	static int N;
	static int[] answer;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(br.readLine());
		
		q = new LinkedList<>();
		visited = new boolean[N + 1];
		answer = new int[N];
		
		adj = new ArrayList<>();
		for(int i = 0 ; i <= N ; ++i) adj.add(new ArrayList<>());
		
		// 인접리스트 초기화 
		for(int i = 0 ; i < N - 1 ; ++i) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
		
			adj.get(from).add(to);
			adj.get(to).add(from);
		}
		
		// 입력된 답안 
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; ++i) answer[i] = Integer.parseInt(st.nextToken());
		
		if(answer[0] != 1) {
			System.out.println(0);
			return;
		}
		
		q.offer(1);
		visited[1] = true;
		
		if(bfs()) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
		
	}

	private static boolean bfs() {
		int idx = 1;
		HashSet<Integer> set = new HashSet<>();
		
		while(!q.isEmpty()) {
			set.clear();
			
			int cur = q.poll();
			
			for(int next : adj.get(cur)) {
				if(visited[next]) continue;
				
				set.add(next);
				visited[next] = true;
			}
			
			int size = set.size();
			
			for(int i = idx ; i < idx + size ; ++i) {
				if(set.contains(answer[i])) q.offer(answer[i]);
				else return false;
			}
			
			idx += size;
		}
		
		return true;
	}
}