DFS 스페셜 저지
면접 대비시간 제한2초메모리 제한512 MB
트리와 정점 순열이 주어질 때, 그 순열이 정점 1에서 시작하는 DFS 방문 순서가 될 수 있는지 판별한다.
문제
정답이 여러 가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드로 정답 여부를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.
정점이 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을 출력한다.