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

백준 16964 파이썬

DFS 스페셜 저지

문제

BOJ에서 정답이 여러 가지인 경우에는 스페셜 저지를 사용 한다.

스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다.

오늘은 스페셜 저지 코드를 하나 만들어 보려고 한다.

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

이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다.

DFS 방문 순서는 dfs 함수에서 //x를 방문이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.

트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구하여라.

입력

첫째 줄에 정점수 N 이 주어진다.

둘째 줄부터는 N-1개의 줄에는 트리의 간선 정보가 주어진다.

마지막 줄에는 DFS 방문 순서가 주어진다.

방문 순서는 1부터 N까지 자연수가 한 번씩 등장한다.

출력

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

 

풀이

1. 주어진 간선 정보를 이용하여 그래프를 만들고 통상적인 DFS 알고리즘을 사용한다.

2. 이때 생각해봐야 할 거는 DFS 인접 노드 탐색하는 순서가 주어진 간선 정보를 순이다. 

예를 들어

1 2
1 3
2 4

이렇게 간선 정보가 주어진다면.

그래프에는 1번 노드 하고 연결된 노드 [2,3] , 2번 노드하고 연결된 노드는 [4]

그러면 무조건 1 ->2 ->3 -> 4를 탐색하게 된다.

만약 이때 1번 노드하고 연결된 노드 순은 [3,2]로 바꾼다면?

1->3->2->4 가된다.

이제 이걸 가지고 주어진 간선 정보로 만들어진 그래프를 주어진 방문 순서를 이용해서 정렬하면 

주어진 방문 순서로 DFS가 순회할 수 있다.

 

주어진 방문 순서가 우선순위가 되는 것이다.

 

코드

import sys

input = sys.stdin.readline

def dfs(g, v, node):
    v[node] = True
    array.append(node)

    for i in g[node]:
        if not v[i]:
            dfs(g, v, i)


n = int(input())
vited = [False] * (n + 1)
array = []

graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
number = list(map(int, input().split()))  # 주어진 순서

for i in range(n+1):
    graph[i].sort(key=lambda x:number.index(x))



if number[0]==1:

    dfs(graph, vited, 1)
    if number == array:
        print(1)
    else:
        print(0)
else:
    print(0)