백준 16964 파이썬 - DFS 스페셜 저지

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

16964번: DFS 스페셜 저지

문제

BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.

정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.

void dfs(int x) {
    if (check[x] == true) {
        return;
    }
    check[x] = true;
    // x를 방문
    for (int y : x와 인접한 정점) {
        if (check[y] == false) {
            dfs(y);
        }
    }
}

 

이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다. DFS 방문 순서는 dfs함수에서 // x를 방문 이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.

트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구해보자.

코드

import sys
n = int(sys.stdin.readline())
arr = [set() for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    arr[a].add(b)
    arr[b].add(a)
order = list(map(int, sys.stdin.readline().split()))
def check():
    if order[0] != 1:
        return 0
    stack = [order[0]]
    for i in range(1, n):
        value = order[i]
        while stack and value not in arr[stack[-1]]:
            stack.pop()
            if not stack:
                return 0
        stack.append(value)
    return 1
print(check())

 

풀이

order에 있는 숫자를 하나씩 가져와 stack 내부의 노드의 arr에 있는지 비교해 없으면 pop()을 해주고 있으면 stack에 그 값을 추가한다. stack에서 pop()을 시켜서 모든 요소가 pop()되었는데 연결된 다음 숫자에 없다는 것은 DFS로 탐색한 순서가 아니라는 뜻이다.