[python] 백준 16964 DFS 스페셜 저지

https://www.acmicpc.net/problem/16964

16964번: DFS 스페셜 저지

문제 해결

• DFS와 BFS를 같이 쓰는 문제
• 입력 값을 하나씩 뽑아서 연결된 간선이 있을 때 다음 입력값과 같은 것이 있으면 계속 dfs를 이어 나간다.
• 끝까지 입력값을 이어나갈 수 있으면 1을 출력 그 전에 dfs가 끝나버리면 0을 출력

CODE

import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10000)

def dfs(plan):
    tmp = plan.popleft()
    if not plan:
        print(1)
        exit()
    visited[tmp] = 1
    for i in range(len(graph[tmp])):
        if plan[0] in graph[tmp] and visited[plan[0]]==0:
            dfs(plan)
    return
if __name__=='__main__':
    n = int(input())
    graph = [[] for _ in range(n+1)]
    visited = [0 for _ in range(n+1)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    plan = deque(map(int, input().split()))

    if plan[0] != 1:
        print(0)
    else:
        dfs(plan)
        print(0)