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

문제링크 https://www.acmicpc.net/problem/16940

 

order 배열에 노드별 우선순위를 담은 다음 그를 이용해 graph를 정렬하는 문제이다

 

order의 인덱스 : 노드 번호

order의 value : 우선순위

 

sort() 함수가 굉장히 다방면으로 쓰일 수 있어 신기했다

 

 

[답코드]

import sys
from collections import deque
input=sys.stdin.readline
 
def bfs(s):
    visited=[False]*(n+1)
    q=deque()
    q.append(s)
    ret=[1]
    visited[s]=True
 
    while q:
        start = q.popleft()
        for node in graph[start]:
            if not visited[node]:
                q.append(node)
                visited[node]=True
                ret.append(node)
    # print(ret)
 
    return ret
 
n=int(input())
graph=[[] for _ in range(n+1)]
# print(graph)
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
result=list(map(int, input().split()))
order=[0]*(n+1)
 
for i in range(len(result)):
    order[result[i]]=i
 
for i in range(1, len(graph)):
    graph[i].sort(key=lambda x:order[x])
# print(graph)
 
ret=bfs(1)
 
if ret==result:
    print(1)
else:
    print(0)