백준 dfs 스페셜 저지

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

16964번: DFS 스페셜 저지

 

 

 

 

 

 

 

<접근방법>

dfs로 방문할 수 있는지의 여부를 묻는 문제입니다.

 

다음 정점으로 이동할 때, 주어진 순서대로 갈 수 있으면 이동하고 마지막 정점에 도착하면

성공했다고 표시해줍니다.

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

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

const int MAX = 100000;
int n, a[MAX + 1];
bool visit[MAX + 1];
int idx = 1;
bool suc;
vector<int> e[MAX+1];

void dfs(int dep, int now) {
	if (idx == n) {
		suc = true;
		return;
	}
	if (visit[now]) return;
	visit[now] = true;

	for (int i = 0; i < e[now].size(); i++) {
		int next = e[now][i];

		if (!visit[next]) {
			if (next == a[idx]) {
				idx++;
				dfs(dep+1, next);
				i = -1;
			}
		}
	}

}

int main() {
	cin >> n;
	for (int i = 0, a, b; i < n-1; i++) {
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	dfs(0, 1);

	if (suc) cout << 1 << '\n';
	else cout << 0 << '\n';
	
	return 0;
}