백준 16964 c++ DFS 스페셜 저지

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

16964번: DFS 스페셜 저지

---

문제

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

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

void dfs(int x) {
    if (check[x] == true) {
        return;
    }
    check[x] = true;
    // x를 방문
    for (int y : x와 인접한 정점) {
        if (check[y] == false) {
            dfs(y);
        }
    }
}

 

이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다. DFS 방문 순서는 dfs함수에서 // x를 방문 이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.

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

입력

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

출력

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

---

#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N;
vector<int> rel[100001];//노드 간 간선
int input[100001];//입력받은 수열
int pre[100001];//자식 이전의 노드(현재 자식의 부모 노드)
int childCount[100001];//자식 노드의 개수

bool dfs()
{
	if (input[1] != 1)//수열 첫번째가 1이 아니면 false
		return false;
	queue<int> q;
	q.push(1);
	int index = 2;//2번째부터 찾아보기 시작할거임
	childCount[1] = rel[1].size();
	for(int i=2;i<=N;i++)
	{//1이 아닌 노드의 자식 개수는 부모노드를 향하는 간선 제외해야 하므로 -1
		childCount[i] = rel[i].size() - 1;
	}
	while (!q.empty())
	{
		int parent = q.front();//현재노드 == parent
		q.pop();
		bool check = false;
		auto it = find(rel[parent].begin(), rel[parent].end(), input[index]);
		if (it != rel[parent].end()) // 찾았다면 
		{
			check = true;
			childCount[parent]--;
			if (rel[input[index]].size() > 1)//자식노드의 자식 수가 1 이상이라면
			{
				pre[input[index]] = parent;//자식 노드의 이전은 현재 노드인 parent
				q.push(input[index]);
			}
			else//자식노드의 자식 수가 0이라면
			{
				int now = parent;
				int cnt = childCount[now];
				while (cnt<1)//cnt가 0보다 크면 그만
				{
					int temp = pre[now];
					now = temp;
					cnt = childCount[now];
				}
                //자식 수가 남아있는 부모노드까지 올라가서 push
				q.push(now);
				
			}
			index++;
			if (index == N)
				return true;
		}
		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 (dfs())
		cout << 1;
	else
		cout << 0;
}

---

https://mun-coding.tistory.com/126

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

해당 문제에서 조금 수정하여 풀었다.

자식노드의 경우 본인이 자식이 없다면 다시 부모로 올라가야 하므로 

int pre[100001] 를 사용했다 (pre[3] == 1 일 경우 3의 부모는 1)