[백준_16964]_DFS스페셜저지_python

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

16964번: DFS 스페셜 저지

BOJ에서 정답이 여러 가지인 경우에는 스페셜 저지를 사용 한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다. 트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구해보자.

입력

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

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

출력

입력으로 주어진 DFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.

입력                   출력

4                         0

1 2

1 3

2 4

1 2 3 4

----------------------------------------------------

문제 해결

처음에 이 문제를 읽고 신나서 정점 방문 순서대로 일치하는지 불일치하는지에 따라 1 혹은 0을 출력을 하는 코드를 짰지만.. 아니었다. 

   - 2 - 5 - 6

1 - 3 - 7

   - 4

위와 같이 1에 2,3,4의 노드가 연결되어 있다고 본다면 (1-2-5-6-3-7-4) 순으로 방문순서를 찾을 수 있다.

하지만 경우에 따라 (1-3-7-2-5-6-4)와 같은 경우도 생각해주어야 한다.

예제 입력의 마지막 줄에는 노드의 번호가 순서대로 주어질 때 깊이 우선 탐색(dfs)을 했을 시에 올바른 방문순서 인지를 묻는 거다.

ex) (1-4-3-7-2-5-4) or (1-2-5-6-4-3-7) or ( 1-3-7-4-2-5-6) 등 예제로 주어졌을 때 dfs로 방문했을 시에 옳은 순서인지 확인해주어야 한다. 

 

고로 예제로 주어진 배열의 값을 기준으로 dfs방문이 성립 가능한 순서인지를 구현하는 게 포인트이다.

 

num = [1,2,3,4]라고 하였을 때 pop()을 사용하여 끝 노드부터 탐색하기엔? 답의 정당성이 보장이 되지 않는다.

문제에서 시작점은 1로 정해놓았기에 무조건 1부터 시작하는 것이고 collections모듈의 deque 자료구조를 사용하여 1번 노드를 시작으로 하여 num.popleft() ->> 현재 노드, num [0] ->> 다음 노드로 생각해준다. 만약 graph [현재 노드 위치] : 인접 노드에 num [0] 값이 있는지를 확인하여 num값이 모두 pop 되어 빈 배열이 되면 방문순서가 맞는 것이기에 1을 출력해주고 배열이 True인데 dfs가 끝났으면 False를 리턴하여 0 혹은 1을 출력해주도록 한다.

(입력으로 주어진 num [0]의 값이 1이 아닌 경우도 예외로 설정해 주어야 한다)

 

import sys
from collections import deque
sys.setrecursionlimit(10**6)

def dfs(ans):
    tmp = ans.popleft()
    if not ans:
        print(1)
        exit(0)
    visited[tmp] = 1
    for i in range(len(graph[tmp])):
        if ans[0] in graph[tmp] and visited[ans[0]]==0:
            dfs(ans)
    return False

input = sys.stdin.readline
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)
ans = deque(map(int,input().split()))
if ans[0] != 1:
    print(0)
    exit(0)
if not dfs(ans):
    print(0)