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

 

문제

16940번: BFS 스페셜 저지

 

 

알고리즘

그래프, 너비 우선 탐색(BFS), 해시셋

 

 

풀이

 

출처: 위키피디아

 

다음 그래프에 대해 (1 2 3 4 5 6 7 8 9 10 11 12) 라는 방문 순서가 있다면 다음과 같이 판별할 수 있다.

시작 노드인 1이 3개의 인접 노드를 가지고 있으므로 다음 3개의 수(2~4번째)는 1의 인접 노드이어야한다.

그 다음 노드인 2가 2개의 인접 노드를 가지고 있으므로 다음 2개의 수(5~6번째)는 2의 인접 노드이어야한다.

...

모든 노드가 위 조건을 만족하면 올바른 순서임을 알 수 있다.

 

표로 나타내면 다음과 같다.

빨간색 숫자가 검사할 숫자

파란색 숫자가 그의 인접한 노드가 위치해야하는 숫자이다.

 

이때 파란색 숫자가 빨간색 숫자의 인접 리스트에 속해있는지 빠르게 검사하기 위해 그래프를 해시셋으로 구현하였다.

빨간색 숫자와 파란색 숫자의 인덱스를 나타내기 위해 2개의 int형 변수를 사용한다.

 

양방향 그래프이므로 인접한 정점 리스트에는 이미 방문한 정점 번호가 들어가있다.

따라서 검사한 노드들은 visited 라는 별도의 해시셋에 넣어두고 (인접한 노드의 수 - 이미 검사한 노드의 수) 만큼만 검사해야한다.

예를 들어 위 표의 두번째 줄에서 2의 인접한 노드에는 1도 포함되어있지만 이미 검사한 숫자이므로 제외한 것이다.

 

* 문제에 시작 정점이 1이라는 조건이 있어 1이 아닌 다른 수가 시작 정점으로 들어오면 0을 출력해야한다.

 

코드

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.List;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

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

		int N = Integer.parseInt(br.readLine());
		
		Set<Integer>[] graph = new HashSet[N + 1];
		for (int i = 1; i <= N; i++)
			graph[i] = new HashSet<>();

		for (int i = 0; i < N - 1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			graph[a].add(b);
			graph[b].add(a);
		}

		List<Integer> sequence = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++)
			sequence.add(Integer.parseInt(st.nextToken()));

		if(sequence.get(0) != 1) {
			System.out.println(0);
			return;
		}
			
		Queue<Integer> queue = new LinkedList<>();
		Set<Integer> visited = new HashSet<>();
		queue.add(1);
		visited.add(1);
		int index = 1;
		int count = 1;
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();

			int size = graph[cur].size();
			
			for (int num : graph[cur]) {
				if (visited.contains(num)) {
					size--;
				}
			}

			for (int i = index; i < index + size; i++) {
				if(i >= N) {
					System.out.println(0);
					System.exit(0);
				}
				int num = sequence.get(i);

				if (!graph[cur].contains(num) && !visited.contains(num)) {
					System.out.println(0);
					System.exit(0);
				}
			}

			if (count == N) break;
			queue.add(sequence.get(count++));
			index += size;
			visited.add(cur);
		}

		System.out.println(1);
	}
}