[알고리즘][Python] 백준(BOJ) 16940 BFS 스페셜 저지_파이썬

 

16940 BFS 스페셜 저지    www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

 

 

문제 풀기 전 공부할 것 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

 

 

 

 

 

풀이 1

<코드>

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    tree = [set() for _ in range(n+1)]
    tree[0].add(1)
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree[a].add(b)
        tree[b].add(a)

    que = [0]
    idx = 0
    answer = list(map(int, input().split()))
    for x in answer:
        while x not in tree[que[idx]]:
            idx += 1
            if idx == len(que):
                return 0
        que.append(x)
        
    return 1

print(solve())

 

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• python은 시간 초과, pypy는 성공

 

<코드>

from collections import deque
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    tree = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    answer = list(map(int, input().split()))
    answer = [a-1 for a in answer]
    if answer[0] != 0:
        return 0
    
    idx = 1
    check = [0] * n
    que = deque([0])
    check[0] = 1
    while que:
        x = que.popleft()
        
        if not tree[x]:
            continue
            
        nex = []
        for i in tree[x]:
            if not check[i]:
                nex.append(i)
                check[i] = 1
        
        l = len(nex)
        for k in range(idx, idx+l):
            if answer[k] in nex:
                que.append(answer[k])
            else:
                return 0
        idx += l
        
    return 1
    
    
print(solve())