백준 16940 c++ BFS 스페셜 저지

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

16940번: BFS 스페셜 저지

---

문제

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을 출력한다.

---

시간초과

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;
vector<int> rel[100001];
int input[100001];

bool bfs()
{
	queue<int> q;
	q.push(1);
	int index = 2;//1번 인덱스는 1로 고정이므로 2번째부터 찾아보기 시작
	int size = rel[1].size();//부모노드 사이즈 변수 지정
	while (!q.empty())
	{
		int parent = q.front();
		q.pop();
		if (parent != 1)//부모노드가 1이 아니라면
		{
			size = rel[parent].size() - 1;//양방향 간선이므로 부모노드로 향하는 간선 하나 제거
		}
		while (size > 0)//부모노드에 속한 자식노드를 다 돌면 끝
		{
			bool check = false;
			for (int i = 0; i < rel[parent].size(); i++)//자식노드를 다 돌면서
			{
				if (input[index] == rel[parent][i])//bfs 다음 원소가 있다면
				{
					check = true;
					if (rel[input[index]].size() > 1)//해당 자식노드도 자식노드가 있다면
					{
						q.push(input[index]);//부모노드가 되기 위해 q 에 push
					}
					index++;//bfs 다음 원소를 찾기위해 +
					size--;//하나 찾았으므로 size 1 감소
				}
			}
			if (!check)//자식노드를 다 찾아봐도 다음에 올 bfs원소가 없다면 리턴
				return false;
		}
	}
	return true;
}

int main()
{
	cin >> N;
	for(int i=0;i<N-1;i++)
	{
		int a, b;
		cin >> a >> b;
		rel[a].push_back(b);
		rel[b].push_back(a);
	}
    
	for (int i = 1; i <= N; i++)
	{
		cin >> input[i];//bfs 배열 입력
	}
    
	if (bfs())
		cout << 1;
	else
		cout << 0;
}

처음에는 무식하게 for문으로 부모노드의 모든 자식들을 돌며 다음 bfs원소가 있는지 없는지를 찾았다 

그러다보니 45%에서 시간초과....

그러다가 0번 인덱스부터 최대 인덱스까지 돌 필요없이 한번에 해당 원소가 있는지 없는지 찾아주는 find를 알게 되었다.

---

맞은코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>//find 쓸 때 필요
using namespace std;

int N;
vector<int> rel[100001];
int input[100002];

bool bfs()
{
    if (input[1] != 1)
		return false;
	queue<int> q;
	q.push(1);
	int index = 2;//2번째부터 찾아보기 시작할거임
	int size = rel[1].size();
	while (!q.empty())
	{
		int parent = q.front();
		q.pop();
		if (parent != 1)
		{
			size = rel[parent].size() - 1;
		}
		while (size>0)
		{
			bool check = false;
			auto it = find(rel[parent].begin(), rel[parent].end(), input[index]);
            //it은 rel[parent]에 input[index]가 있다면 해당 index를 나타냄
			if (it!=rel[parent].end()) // 찾았다면 
            //find를 통해 원하는 값을 못찾았다면 it = rel[parent].end() 가 됨
			{
				check = true;
				if (rel[input[index]].size() > 1)
				{
					q.push(input[index]);
				}
				index++;
				size--;
			}
			if (!check)
				return false;
		}
	}
	return true;
}

int main()
{
	cin >> N;
	for(int i=0;i<N-1;i++)
	{
		int a, b;
		cin >> a >> b;
		rel[a].push_back(b);
		rel[b].push_back(a);
	}
	for (int i = 1; i <= N; i++)
	{
		cin >> input[i];
	}
	if (bfs())
		cout << 1<<'\n';
	else
		cout << 0<<'\n';
}

자식노드를 찾는 부분 외에는 동일하다