[백준-파이썬] 16940 : BFS 스페셜 저지

문제 보러 가기

많이 틀리다가 맞았다!!!

틀렸던 이유 🙆‍♀️

1. 시작 정점 1에서 시작하지 않는 경우도 들어올 수도 있는 것을 체크하지 않았다.
2. 단순히 깊이가 같은 것만 체크하면 안된다. 진짜 큐처럼, 순서도 고려해야 한다.

2에 대해서 좀 더 설명하겠다.
처음에는 깊이만 같으면 다 되는 줄 알았다..!
그래서 딕셔너리를 이용해서 각 깊이 별로 자식을 저장했다.
깊이 1일 때: 1
깊이 2일 때 : 2, 3, 4
깊이 3일 때: 5, 6, 7
입력으로 주어진 BFS 방문 순서를, 각 깊이에 있는 요소들의 길이만큼씩 잘라서 둘다 set으로 만들었다. 두 set이 같은지 판단했다.
이렇게 했더니 50%정도에서 틀렸다.
만약에 1-> 3-> 4-> 2가 들어왔으면, 3의 자식들, 4의 자식들, 2의 자식들 순서대로 나와야 하는 데 그걸 고려하지 못했기 때문이었다.
그걸 고려했더니 맞았다 💕 (이걸 고려해야 한다고 알려주신 스터디원 분 덕분에 풀었다 !! ㅎㅎ )

코드 👩‍💻

import collections
import sys

input = sys.stdin.readline


def bfs():
    q = collections.deque()
    q.append(1)  # 시작 정점 1
    visited[1] = 1

    while q:
        x = q.popleft()
        for y in abj[x]:
            if visited[y] != 0: continue
            visited[y] = visited[x] + 1
            children[x].append(y)
            q.append(y)

N = int(input())
abj = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    abj[a].append(b)
    abj[b].append(a)

children = collections.defaultdict(list)
visited = [0] * (N + 1)

res = list(map(int, input().split()))

if res[0] != 1:  # 시작 정점이 1이 아니면
    print(0)
else:
    bfs()

    q = collections.deque()
    q.append(1)
    idx = 1

    while q:
        tmp = q.popleft()

        a = set(children[tmp])

        len_a = len(a)
        b = res[idx:idx + len_a]
        q.extend(b)
        b= set(b)
        idx += len_a

        if a != b:
            print(0)
            break
    else:
        print(1)