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

백준 16964번

최종 제출 코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input().rstrip())
array = [[] for _ in range(n+1)]

for i in range(n-1):
  a, b = map(int, input().split())
  array[a].append(b)
  array[b].append(a)

result = deque(map(int, input().split()))
visited = [0 for _ in range(n+1)]
parent = deque(0 for _ in range(n+1))
stack = []
queue = deque()

start = 1
visited[start] = 1
queue.append(start)

# bfs를 통해 노드의 부모를 저장하는 list생성
# 필요한건 부모 list 이기 때문에
# dfs를 사용하든 bfs를 사용하든 상관없을 것이라고 판단해서
# 재귀가 없는 bfs를 선택해 문제풀이
while queue:

  node = queue.popleft()

  for ele in array[node]:
    if visited[ele] == 0:
      parent[ele] = node
      visited[ele] = 1
      queue.append(ele)

# 입력받은 result가 dfs를 만족하는지 체크하는 함수
def check():
  # start node를 먼저 stack에 집어넣음
  stack.append(start)
  # result의 두번째 원소부터 문제풀이 논리를 적용하여 검사
  for i in range(1, len(result)):
    if stack[-1] != parent[result[i]]:
      while stack[-1] != parent[result[i]]:
        stack.pop()
        if not stack: return 0
    stack.append(result[i])
  return 1

print(check())

.

✔ 문제풀이

◼ 먼저 parent 리스트 생성

• 노드 i의 부모 노드를 저장하는 리스트
• 부모 노드는 bfs로 탐색하든, dfs로 탐색하든 동일하기 때문에 재귀호출이 발생하지 않는 bfs를 활용하여 parent 리스트 생성

◼ stack을 활용하여 result가 dfs를 따르는지 검사

1. 먼저 start node를 stack에 넣음
2. 그 다음 result의 두 번째 원소부터 dfs의 원리를 따르는지 검사

• result[i]가 stack의 가장 마지막 원소의 자식이라면 stack.append(result[i])
• 자식이 아니라면 stack에서 부모를 만날 때까지 stack의 원소를 pop
• dfs에 따라 제대로 노드를 방문했다면 이미 탐색이 완료된 부분 트리는 제거해도 무관
• 제대로 방문하지 않았다면, 제 때 방문하지 않은 노드는 나중에 자신의 부모를 찾을 수 없게 됨
  ⇒ stack이 비게됨
• 제대로된 순서로 노드를 방문하면 stack에 반드시 마지막에 방문하는 원소의 조상이 남음
• stack의 길이를 검사하여 0이면 0, 아니면 1을 return

.

✔ 예시

.
1. 제대로된 방문

• 1 2 4 6 7 8 5 3
• 파란색 숫자는 이번 순서에 append되는 원소
• 빨간색 숫자는 이번 순서에 pop되는 원소
  

..
2. 잘못된 방문

• 1 2 4 6 7 8 3 5
• 노드 5가 들어가기 전에 stack이 비어 0이 return됨