백준 16964번 DFS 스페셜 저지

문제 링크입니다: https://www.acmicpc.net/problem/16964

16964번: DFS 스페셜 저지

DFS가 진행될 때 형제 노드들이 정렬이 되지 않은 상태에서 진행되므로 DFS 진행 순서를 기록하는 것이 중요합니다.

이후에는 각 노드에 연결된 노드들을 DFS 진행 순서를 기준으로 정렬을 한 뒤 DFS를 진행했을 때 순서가 같은지 여부를 판단해주면 되는 문제였습니다.

순서가 다를 경우 바로 프로그램을 종료하기 위해 exit(0) 문법을 사용했습니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	const int ROOT = 1;
	const int MAX = 1e5 + 1;
	int N;
	int idx;
	vector<int> tree[MAX];
	bool visited[MAX];
	int expected[MAX];
	int dfsOrder[MAX];
	bool cmp(int a, int b)
	{
	return dfsOrder[a] < dfsOrder[b];
	}
	void func(int node)
	{
	if (node != expected[idx++])
	{
	cout << 0 << "\n";
	exit(0);
	}
	for (int i = 0; i < tree[node].size(); i++)
	{
	int next = tree[node][i];
	if (visited[next])
	{
	continue;
	}
	visited[next] = true;
	func(next);
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; i++)
	{
	int a, b;
	cin >> a >> b;
	tree[a].push_back(b);
	tree[b].push_back(a);
	}
	for (int i = 0; i < N; i++)
	{
	cin >> expected[i];
	dfsOrder[expected[i]] = i + 1;
	}
	for (int i = 1; i <= N; i++)
	{
	sort(tree[i].begin(), tree[i].end(), cmp);
	}
	visited[ROOT] = true;
	func(ROOT);
	cout << 1 << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2019

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~