백준 BOJ 16964 - DFS 스페셜 저지

우선순위가 특별한 DFS이다.

 

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

16964번: DFS 스페셜 저지

방문 순서에 맞게 DFS로 탐색할 수 있는지 체크해야 하는 문제.

방문 순서에 맞게 탐색시키기 위해서,

방문 순서를 "우선순위" 화 시켜서

탐색할때 우선순위가 가장 높은 == 방문 순서에 가장 가까운 형태로 DFS를 진행하면 된다.

방문 순서를 관리하는 배열을 만들고 정렬 시에 참고하도록 하게 작성해서 해결했다.

 

DFS 함수는 문제에서 주어진거 그대로 사용해도 큰 문제가 안된다.

결국 저 y에 들어가는 값의 우선순위를 정해주는 문제이기 때문이다.

 

두 std::vector 간 값이 같은지 체크하는걸 == 으로도 처리할수 있는지 몰랐다.

원래 반복문 작성해서 비교했었는데 지식이 늘었다.

 

#include <bits/stdc++.h>
using namespace std;

bool vis[123456] = {0};
int pri[123456] = {0}; // 우선순위. 

vector<int> g[123456];
vector<int> ans;
vector<int> in;

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

void dfs(int x){
	if(vis[x]) return;
	vis[x] = true;
	
	ans.push_back(x);
	
	for(int y : g[x]) if(!vis[y]) dfs(y);
	return;
}

int main(){
	int N,a,b,k;
	cin >> N;
	for(int i=0; i<N-1; i++){
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	for(int i=0; i<N; i++){
		cin >> k;
		in.push_back(k);
		pri[k] = i;
	}
	
	for(int i=0; i<=100000; i++) sort(g[i].begin(), g[i].end(), cmp);
	
	dfs(1);
	
	cout << (ans == in);
	return 0;
}