[백준][Python] 16940 BFS스페셜저지

온전하게 BFS를 순서까지 맞춰서 검사하는 방법에는 무엇이 있을까?

실제 BFS를 돌려 그 순서를 기록하는 방법?

노드 순회 순서에따라서 천차만별일 것이다.

그럼 레벨을 정해 레벨단위로 추적하는 방법?

레벨3이 레벨2인 어떤 노드에서 큐에 삽입됐는지까지 추적하지 않는다면 완벽한 검사는 불가능하다.

 

하지만 아래 코드는 완벽하게 검사해야하는 리스트를 실제 BFS의 작동방식처럼 num이 기존의 queue에 삽입된 노드로부터 왔는지를 순서대로 검사한다. 만약 순서가 잘못되어잇다면 레벨상 맞더라도 완벽하게 검열당한다.

BFS는 단순히 레벨 0에서 갈수있는 레벨 1들을 정하고 레벨2들을 정해 검사하는 방식이 아니라

큐를 이용하는 FIFO의 검사방식이라는걸 늘 명심해야 할 것이다.

 

내일은 DFS스페셜 저지를 풀예정인데 기대된다.

# 정점 1~N,양방향 그래프
# 1. 큐에 시작정점을 넣는다. 시작은 1이다 1을 방문했다고 처리한다.
# 2. 큐가 비어있지 않은동안 반복. 큐꺼내서 x 방문하지 않은 연결된 정점 y를 큐에 어팬드.
import sys
input = sys.stdin.readline

N = int(input())
tree = {i:[] for i in range(1,N+1)}
tree[0] = [1]

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

seqs = list(map(int,input().split()))
que=[0]
idx=0
# que에 넣는 것은 검사해야하는 수열의 숫자.
for num in seqs:
    # que에 있는 숫자의 다음에 와야하는 숫자를 가져와 
    # seqs의 num과 비교해 일치하면 que에 넣고 
    # 일치하지 않으면 idx를 늘려서 que의 다음 숫자가 num을 포함하는지 검사하는 방식.
    # idx가 큐의 마지막까지 왔는데 num이 큐에 있는 숫자의 다음숫자(tree집합)에 포함되지 못했다면
    # BFS에 따르지 않았다는 뜻. 아래 반복문은 온전히 BFS의 큐 삽입 순서에 따라 작동함.
    # num이 큐 내부에 있는(이미 BFS검사가 끝난) 노드의 tree에 있다면 큐에 넣고 아니면 큐 내부의 다른 숫자를 검사하는 방식.
    # 큐 내부에서 num으로 이어지는 방법이 없다면 BFS가 될 수 없는 수열이라는게 증명.
    while num not in tree[que[idx]]:
        idx+=1
        if idx == len(que):
            print(0)
            exit()
    que.append(num)
print(1)