[알고리즘] 백준 3665(파이썬)

처음에 기본적인 위상 정렬의 문제로 생각하여 바뀐 노드의 값들의 진입차수와 진출차수만 서로 바꿔주고 진입차수 - 진출차수 = -1 인 노드가 결국 맨 앞의 노드이기 때문에 이 값이 -1인 순서대로 뽑았다. 하지만 이렇게 하면 실상 순위를 정할 수 없는 경우를 찾기 힘들어진다. 따라서 바꾸는 노드의 index차이만큼 앞 노드는 진입차수를 늘리고 뒤 노드는 진출차수를 늘렸다. 이렇게 되면 현재 차이나는 인덱스만큼 이동하는 효과를 얻게되고 최종 본인의 등수는 현재 index - 추가 진입차수 + 추가 진출차수이 된다. 만약 이 값이 같은 노드가 있다면 곧 중복이기 때문에 IMPOSSIBLE을 띄우면 된다.

import sys
from collections import deque
test = int(input())

for _ in range(test):
    n = int(input())
    ranked = list(map(int, sys.stdin.readline().split()))

    check = [0 for k in range(n+1)]
    check_out = [0 for k in range(n+1)]

    change = int(input())


    for i in range(change):
        a, b = map(int, sys.stdin.readline().split())

        if ranked.index(a) < ranked.index(b):
            check[a] += 1
            check_out[b] += 1
            
        else:
            check[b] += 1
            check_out[a] += 1
            
    ans = [0 for i in range(n)]

    queue = deque([])


    dd = {}
    for i in range(len(ranked)):
        tar = ranked[i]
        dd[tar] = i + check[tar] - check_out[tar]

    s = set()
    for kkk in dd:
        s.add(dd[kkk])
        ans[dd[kkk]] = kkk

    if len(s) == n:
        print(*ans)
    else:
        print("IMPOSSIBLE")