[백준] 16964번 DFS 스페셜 저지 ★★★

💡문제접근

• 주어진 DFS 방문 순서대로 탐색을 할 수 있는지에 대해 묻는 문제였는데 일반적인 DFS 코드를 떠올려 인접 노드의 정점 방문 순서를 오름차순/내림차순 정렬을 수행한 결과를 각각 따로 구한 다음 주어진 DFS 방문 순서와 일치하면 1을 출력하는 방식으로 코드를 작성했지만 WA와 TLE를 수도 없이 반복했다.
• 위의 접근 방법에 문제가 있는지 확인하기 위해 질문게시판을 확인했는데 deque 자료구조를 사용해서 앞에서부터 노드를 받아와 해당 노드의 인접한 노드들에 대해 탐색을 진행하면서 만약 deque가 비어있게 된다면 1을, 아니라면 False를 반환하는 방식의 코드가 눈에 띄었다. 해당 코드에 대해 숙지한 다음 코드를 작성했는데 정말 오랜 시간이 걸렸던 문제였다.

💡코드(메모리 : 280232KB, 시간 : 2852ms, PyPy3로 제출)

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
# 연결리스트로 표현한 graph
for _ in range(1, N):
    a, b = map(int, input().strip().split())
    graph[a].append(b)
    graph[b].append(a)

def DFS(sequence, start):
    element = sequence.popleft()
    if not sequence:
        print(1)
        sys.exit(0)
    visited[element] = True
    for i in range(len(graph[element])):
        if sequence[0] in graph[element] and not visited[sequence[0]]:
            DFS(sequence, sequence[0])
    return False

sequence = deque(map(int, input().strip().split()))
if sequence[0] != 1:
    print(0)
    sys.exit(0)
if not DFS(sequence, 1):
    print(0)

💡소요시간 : 2h ↑