[백준 / BFS] #16940 BFS 스페셜 저지 (java)

문제

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

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

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

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

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

입력

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

출력

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

 

 

[문제접근]

다양한 시도 가능

1. 연결된 노드 갯수 기준  / 2. depth기준

 

그러나 문제의 핵심은 

결국 어떠한 정점에 대하여 

1) 자신의 부모 정점이 무엇인가

2) 자신의 자식 정점은 몇개가 있는가

에 대한 값들을 전부 아는 상태로 시작해야 한다. 

 

처음에 BFS를 돌면서 부모 노드와 자식 노드의 갯수를 전부 기록해 둔다. 

그리고 주어진 순서를 순회하면서 현재 노드가 기록했던 부모 노드와 일치하는지 비교하면 된다. 

 

parentQueue는 부모 노드만을 집어넣는 전용 큐이다. 

childSize라는 자식 노드의 갯수가 1 이상인 노드들은 전부 parentQueue에 저장되고, 자식 노드가 전부 나온 후에야 큐에서 빠져나온다. 

만약 연속해서 나오는 자식 노드의 갯수가 저장된 childSize와 일치하지 않는다면 불가능한 (올바르지 않은) BFS라는 뜻이 된다. 

 

[코드]

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

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

public class Main {

	static private class Node {
		int parent;
		int childSize;
		
		public Node(int parent, int childSize) {
			this.parent = parent;
			this.childSize = childSize;
		}
	}
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		List<List<Integer>> arr = new ArrayList<>();
		Node[] node = new Node[n+1];
		
		for (int i=0; i<n+1; i++) {
			arr.add(new ArrayList<>());
			node[i] = new Node(0, 0);
		}
		
		for (int i=0; i<n-1; i++) {
			String[] input = br.readLine().split(" ");
			int v1 = Integer.parseInt(input[0]);
			int v2 = Integer.parseInt(input[1]);
			
			arr.get(v1).add(v2);
			arr.get(v2).add(v1);
		}
		
		String[] order = br.readLine().split(" ");
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[n+1];
		
		queue.add(1); // 시작 정점은 1이라고 했으므로
		visited[1] = true;
		
		//BFS 돌면서 부모 노드, 자식 노드 갯수 구하기
		while(!queue.isEmpty()) {
			int now = queue.poll();
			
			arr.get(now).forEach(it -> {
				if (!visited[it]) {
					visited[it] = true;
					node[it].parent = now;
					node[now].childSize++;
					queue.add(it);
				}
			});
		}
		
		// 노드가 A->B 순서대로 나왔다면 뒤에서 A자식노드 -> B 자식노드 순으로 나와야 한다.
		// parentQueue에는 order 순서대로 담으면서 자식노드가 전부 나올 때까지 기다렸다가 부모 노드를 교체해준다.
		Queue<Integer> parentQueue = new LinkedList<>();
		int parent = 1;
		for(int i=1; i<n; i++) {
			int now = Integer.parseInt(order[i]);
			if(parent != node[now].parent) {
				System.out.println(0);
				return;
			}
			
			if(node[now].childSize > 0) parentQueue.add(now);
			node[parent].childSize--;
			if(node[parent].childSize == 0 && i < n-1) parent = parentQueue.poll();
		}
		System.out.println(1);

	}

}

 

 

 

[출처]

뱀귤님 블로그

https://bcp0109.tistory.com/85?category=847904

백준 16940번. BFS 스페셜 저지 (Java, Kotlin)

 

[링크]

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

16940번: BFS 스페셜 저지