파이썬 백준 3665 최종 순위

import sys
input = sys.stdin.readline
from collections import deque
 
testcase = int(input())
for j in range(testcase) :        
    n = int(input())
    V = {}
    parent = [0 for i in range(n + 1)]
    for i in range(1, n + 1) : 
        V[i] = []
    l = list(map(int, input().split()))
    for i in range(n) : 
        V[l[i]] = l[i+1:]
        parent[l[i]] = i
    copy = parent[:]
    m = int(input())
    for i in range(m) : 
        v1, v2 = map(int, input().split())
        if copy[v2] < copy[v1] : 
            v1, v2 = v2, v1
        V[v2].append(v1)
        parent[v1] = parent[v1] + 1
        parent[v2] = parent[v2] - 1
 
    que = deque()
    for i in range(1, n + 1) : 
        if parent[i] == 0 : 
            que.append(i)
    if len(que) != 1 : 
        print("IMPOSSIBLE")
    ans = []
    while que : 
        now = que.popleft()
        ans.append(now)
        for next in V[now] : 
            parent[next] = parent[next] - 1
            if parent[next] == 0 : 
                que.append(next)
        if len(que) != 1 and len(ans) != n : 
            print("IMPOSSIBLE")
            break
    if len(ans) == n : 
        print(*ans)
 

line 5 ~ 15

인풋대로 연결관계 dict V를 작성한다. 어느 두 점이 바뀔지 모르므로, 자기 뒤의 모든 점을 V에 넣는다. (line 14)

degree를 카운트하는 리스트 parent도 뒤 점들의 개수만큼 더한다.

 

line 16 ~ 24

서로 바뀔 두 점 v1, v2를 인풋받으면, 기존 앞 점의 degree는 -1하고, 기존 뒤 점의 degree는 +1한다.

그리고 뒷점에서 앞점으로의 연결관계도 추가한다.

 

line 26 ~ 44

기존의 정렬은 자기 뒤의 모든 점을 V에 넣었으므로, degree가 0, 1, 2, 3, ... n-1이다.

즉 degree가 0인 점을 큐에 넣는다면 큐에는 항상 1개만 들어왔다가 나오면서 큐가 길이 0 or 1을 유지한다.

인풋대로 점을 바꾼 순서도 올바른 위상을 가졌다면 위와 같이 큐의 길이가 유지될 것이다.

초기에 큐에 들어간 점이 1개가 아니거나 위상정렬 도중 큐에 1개보다 많은 점이 들어온다면, 이는 잘못된 정렬이므로 IMPOSSIBLE을 출력하며 break한다.

만약 ans의 길이가 n이 될때까지 break되지 않고 잘 작성되었다면 이는 올바른 정렬이므로 ans를 출력한다.