BFS 스페셜 저지

알고리즘 구분 : BFS

문제

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

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

큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다.
큐가 비어 있지 않은 동안 다음을 반복한다.
큐에 들어있는 첫 정점을 큐에서 꺼낸다. 이 정점을 x라고 하자.
x와 연결되어 있으면, 아직 방문하지 않은 정점 y를 모두 큐에 넣는다. 모든 y를 방문했다고 처리한다.
2-2 단계에서 방문하지 않은 정점을 방문하는 순서는 중요하지 않다. 따라서, BFS의 결과는 여러가지가 나올 수 있다.

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

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

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

예제 입력 1
4
1 2
1 3
2 4
1 2 3 4
예제 출력 1
1
올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다.

예제 입력 2
4
1 2
1 3
2 4
1 2 4 3
예제 출력 2
0

문제 풀이

전형적인 BFS과정을 증명하는 과정을 파악하는 문제이다.
조심해야 하는 첫 번째 부분은 정답이 여러 개가 될 수 있다는 부분이다.
정답이 여러 개가 될 수 있으므로, 주어진 방문 조건이 가능한지 여부를 일일이 확인하는 방식으로 진행하여야 한다.
두 번째 부분은 시작점은 반드시 1이여야 한다는 것이다. 이 부분은 BFS()함수를 실행하기 전의 종료 조건을 구현하는데 필요하다. 즉, 방문 노드를 입력받을때, 첫 번째 값이 1이 아니라면 문제의 주어진 조건을 위반하기 때문에, 0을 출력해야 하며, 만약 1과 연결된 노드가 아무것도 없다면, BFS를 시작할 수 없기에 0을 출력하게 된다.

BFS함수를 구현할 때, 일반적인 BFS함수와의 차별점은 set자료형을 이용한 중복 제거 구현이다.
예제에서도 볼 수 있지만, 순서가 1, 2, 3, 4도 될 수 있고, 1, 3, 2, 4가 될 수 있는제 일반적인 순차 반복문을 이용한 BFS에서 방문 순서와의 비교를 진행하게 된다면, 1, 3, 2, 4는 불가능한 순서로 간주할 수 있게 되기 때문이다.
그렇기에, set자료형 변수를 이용하여 현재 노드에서 연결이 가능한 노드들을 찾은 뒤, set자료형 변수에 insert하고 방문처리를 해놓는다. 당연히 이미 방문했던 것들은 집합으로 넣을 수 없도록 조건을 구현해 놓아야 한다.

이후, 집합의 크기만큼 반복하면서, 하나씩 find() 메소드를 이용해 찾아서, order큐에서 pop시키며, BFS를 진행하는 q에 삽입하는 과정을 진행하면 된다.

이후, 모든 과정이 정상적으로 끝났다면, 1을 출력하도록 하면 된다. 만약 방문 순서에서의 노드가 현재 set자료형 변수에 없다면, 0을 출력하도록 하면 된다.

틀린 접근
1. 모든 경우의 수를 다 특정 변수에 저장하여, 마지막에 비교하여 해당 경우의 수 중 하나와 일치하는 문제의 Input이 있을 경우 정답을 출력하도록 구현하고자 하였다. 그러나 visited 배열만 해도 수십 개를 만들어야 하므로, 메모리 제한을 초과하게 되어 구현이 불가능하다고 판단하였다.
2. visited배열을 따로 선언하지 않고, 주어지는 방문 순서를 queue order로 입력받아,
order.front()값이 현재 위치에서 연결된 노드 중 하나가 될 수 있는지를 파악하는 조건문만을 이용하여 구현하고자 하였다. 너무 생각을 많이 한 나머지, BFS의 기본 정의 자체를 무시한 접근법이 되고 말았다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

int n;
int visited[100001];
vector<int> graph[100001];
queue<int> order;
void bfs();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for(int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	for(int i = 0; i < n; i++) {
		int input;
		cin >> input;
		order.push(input);
	}
	
	if(graph[1].size() == 0) {
		cout << 0 << endl;
	}
	else if(order.front() != 1) {
		cout << 0 << endl;
	}
	else {
		bfs();
	}
	
	return 0;
}

void bfs() {
	int now;
	queue<int> q;
	
	q.push(order.front());
	visited[order.front()] = true;
	order.pop();
	while(!q.empty()) {
		now = q.front();
		q.pop();
		
		set<int> s;
		
		for(int i = 0; i < graph[now].size(); i++) {
			if(visited[graph[now][i]]) {
				continue;
			}
			visited[graph[now][i]] = true;
			s.insert(graph[now][i]);
		}
		
		for(int i = 0; i < (int)s.size(); i++) {		
			if(s.find(order.front()) == s.end()) {
				cout << 0 << endl;
				return;
			}
			else {
				q.push(order.front());
				order.pop();
			}
		}
	}
	
	cout << 1 << endl;
}
  
/*
vector<vector<int>> graph(100001, vector<int>(0, 0));
위의 방법이 아닌 아래의 방법으로 선언하자.
vector<int> graph[100001];
*/

• 문제 출처 : https://www.acmicpc.net/problem/16940
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.