16940 - BFS 스페셜 저지

from collections import deque

n = int(input())

graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
answer = list(map(int, input().split()))
visit = [False] * (n + 1)
depth = [0] * (n + 1)
parent = [0] * (n + 1)
order = [0] * (n + 1)
for i in range(n):
    order[answer[i]] = i


def dfs(node, d):
    visit[node] = True
    depth[node] = d

    for next in graph[node]:

        if not visit[next]:
            dfs(next, d + 1)
            parent[next] = node


dfs(1, 0)

for i in range(n - 1):

    if depth[answer[i]] > depth[answer[i+1]]:
        print(0)
        break
    if order[parent[answer[i]]] > order[parent[answer[i+1]]]:
        print(0)
        break
else:
    print(1)

전제 : BFS로 순회 할 때 현재 정점의 깊이를 저장하면 그 배열은 오름차순으로 정렬이 된다.

위 전제를 기반으로 문제를 풀었으며 몇 가지 예외를 처리해주어야 한다.

예외 1. 정점의 깊이가 같아도 순서가 옳지 못한 경우를 예외처리 해주어야 한다.

이와 같은 그래프에서 BFS로 순환한 결과가 1 3 2 4 5 6 이라고 하고 이들의 깊이를 나타내면 0 1 1 2 2 2로 깊이는 오름차순으로 나타내게 된다.

그렇지만 1 3 2를 순회하면 6 4 5 혹은 6 5 4 순으로 순회를 해야하는데 4 5 6이면 제대로 된 BFS 순회가 아니게 된다.

따라서 이를 해결하기 위해서 현재 노드의 부모노드의 순회 순서를 비교해서 문제를 해결하였다.

예외 2. 문제에서 시작 정점은 1이라고 했으나 BFS 순회 결과가 1로 시작하지 않는 예외를 처리해주어야 한다.