백준 16940번 : BFS 스페셜 저지 (Java)

 문제

https://www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

16940 BFS 스페셜 저지

 

 구현 방법

BFS 알고리즘 문제입니다.
문제를 보면 정점을 방문하는 순서는 중요하지 않아서 BFS 의 결과는 여러 가지가 나올 수 있다고 명시되어 있습니다.
방문 순서는 중요하지 않다는 말은 같은 레벨에서 삽입하는 정점의 순서가 중요하지 않다는 말입니다.

여기서 주의할 점은 한 정점에서 이동하는 정점들과 또 다른 정점에서 이동하는 정점들의 순서가 섞이면 안 됩니다.
예를 들어 2번, 3번 정점이 큐에 있고 2번은 4번, 5번 정점과 연결, 3번은 6번, 7번 정점과 연결되어있다고 가정할 때
4, 5, 6, 7  or  5, 4, 6, 7  or. 4, 5, 7, 6  or  5, 4, 7, 6 순서는 가능하지만
4, 6, 5, 7 과 같이 순서가 섞이는 것은 불가능합니다.

따라서 정점을 큐에 삽입하기 전에 방문하려는 정점이 해당 레벨에 있는지, 정점끼리의 순서는 맞는 지 검사를 해줍니다.
인덱스 변수를 생성하여 현재까지 검사한 인덱스 다음부터 내가 이동할 정점의 개수까지 방문 순서를 탐색합니다.
저장해 둔 정점이 범위 내에 있는지 확인하고 범위 내에 있다면 큐에 삽입합니다.
방문 순서대로 탐색한 후 큐에 삽입하기 때문에 정점이 범위 내에 있는지, 이동하려는 정점끼리 섞이지 않았는지만 확인해주면 끝 😝

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

 

 구현 코드

package BOJ.Gold;

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 B16940_BFS스페셜저지 {
	static int N, idx = 1, ans[];
	static boolean visit[];
	static Set<Integer> set = new HashSet<>();
	static Queue<Integer> queue = new LinkedList<>();
	static List<List<Integer>> list = new ArrayList<>();
	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());
		visit = new boolean[N+1];
		ans = new int[N];
		for (int i=0;i<=N;i++) {
			list.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());
			// 간선 저장
			list.get(from).add(to);
			list.get(to).add(from);
		}
		st = new StringTokenizer(br.readLine());
		for (int i=0;i<N;i++) {
			ans[i] = Integer.parseInt(st.nextToken());
		}
		// 시작은 무조건 1
		if (ans[0] != 1) {
			System.out.println(0);
			System.exit(0);
		}
		queue.offer(1);
		visit[1] = true;
		System.out.println(bfs());
	}
	
	static int bfs() {
		while(!queue.isEmpty()) {
			int now = queue.poll();
			for (int next : list.get(now)) {
				// 연결 되어 있는 정점 중 방문하지 않은 곳 방문
				if (!visit[next]) {
					visit[next] = true;
					set.add(next);
				}
			}
			
			// 해당 레벨에서 추가된 정점들 사이즈
			int size = set.size();
			
			// 지금까지 검사 된 인덱스에서 추가된 인덱스까지 값이 있는지 검사
			for (int i=idx;i<idx+size;i++) {
				// 값이 있다면 큐에 삽입
				if (set.contains(ans[i])) queue.offer(ans[i]);
				// 없다면 방문 순서가 올바르지 않으므로 0 리턴
				else return 0;
			}
			
			// 검사 완료 후 인덱스 추가
			idx += size;
			set.clear();
		}
		return 1;
	}
}

 

정답!