백준 16964 DFS 스페셜 저지

문제링크

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

문제

풀이

1. 주어진 dfs방문 순서에 따라 방문 우선순위 정하기.
   

2. 이를 기준으로 sort정렬 알고리즘에 적용.
   각 정점에서 인접 정점들을 정렬.
   

   미리 정렬을 시켜뒀기 때문에 각 정점에서는 인접 정점을 앞에서부터 방문했을때 주어진 방문순서와 동일한 결과가 나와야 한다.

시행착오

정렬에 관한 아이디어는 떠올렸으나 어떤식으로 우선순위를 주어야 할지 고민하던 중 인터넷에서 힌트를 얻어 적용시켰다.
또 구현상 사소한 실수도 있었다.

ex)

 1) 가장 처음 호출하는 함수는 dfs(1)이어야 한다는 조건 무시

 2) 정점은 1~100000의 범위인데 정렬 시 for문에서 0번 정점부터 접근
..

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
#define MAX_NODE 100001
vector<int> tree[MAX_NODE];
int	order[MAX_NODE];
int pri[MAX_NODE];
bool vi[MAX_NODE];
int n;

bool cmp(int a, int b) {
	return pri[a] < pri[b];
}

bool solution(int now, int& idx) {
	for (int i = 0; i < tree[now].size(); i++) {
		int next = tree[now][i];
		if (vi[next]) continue;
		vi[next] = true;

		if (next != order[++idx]) return false;
		else {
			if(!solution(next, idx)) return false;
		}
	}
	return true;
}

int main() {
	ios::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 >> order[i];
		pri[order[i]] = i + 1;
	}


	for (int i = 1; i <= n; i++) {
		sort(tree[i].begin(), tree[i].end(), cmp);
	}

	int idx = 0;
	if (order[0] == 1) {
		vi[1] = true;
		cout << solution(order[0], idx);
	}
	else cout << 0;
}

후기

sort 함수의 새로운 활용방법에 대해 알았다.
또, 이 문제는 스택을 활용한 풀이도 가능하다.
다시한번 풀어보자