16940: BFS 스페셜 저지

• 처음에는 같은 depth의 원소들끼리 sort() 하여 같다면 1을 출력하도록 구현했음
• 근데 이렇게 하면 부모 노드들의 순서에 따라 자식 노드들의 순서도 달라지기 때문에 틀린 방식임

import sys
from collections import deque

def bfs():
    queue = deque([])
    queue.append(1); visit[1] += 1

    while queue:
        curr = queue.popleft()

        for after in adjacent[curr]:
            if visit[after] == -1:
                queue.append(after)
                visit[after] = visit[curr] + 1
                children[curr].add(after) #curr의 child는 after임


N = int(input())
adjacent = [[] for _ in range(N+1)]
for n in range(N-1):
    tmp = list(map(int, sys.stdin.readline()[:-1].split(' ')))
    adjacent[tmp[0]].append(tmp[1])
    adjacent[tmp[1]].append(tmp[0])
ans = list(map(int, sys.stdin.readline()[:-1].split()))

visit = [-1] * (N+1)
children = [set() for _ in range(N+1)]
bfs()

next_idx = 1
for i in ans:
    if next_idx == N:
        break

    children1 = set(ans[next_idx:next_idx+len(children[i])])
    children2 = children[i]

    if children1 != children2:
        print(0)
        exit()

    next_idx += len(children[i])
print(1)

• 따라서 children 이라는 set으로 구성된 list를 생성하여, 부모 노드들의 자식 노드들을 저장해줌
• 만약 ans에서, next_idx ~ next_idx + len(children[i])인 부분을 set으로 변경한 결과와 children[i]이 같지 않다면 print(0)을 해주고 exit()
• ans에서, next_idx ~ next_idx + len(children[i])인 부분을 set으로 변경한 결과와 children[i]이 같지 않은 경우가 없다면 break 해주고 print(1)