[ 백준 ][ 골드1 ] 3665번 - 최종 순위 ( 파이썬 Python )

링크 : https://www.acmicpc.net/problem/3665

3665번: 최종 순위

 

코드

---

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    rank = list(map(int,input().split()))
    
    degree = [0] * (n + 1)
    for i,v in enumerate(rank):
        degree[v] = i
        
    graph = [*degree]
    m = int(input())
    for _ in range(m):
        a,b = map(int,input().split())
        if graph[a] < graph[b]:
            a,b = b,a
        degree[a] -= 1
        degree[b] += 1

    res = [0] * n
    for i,v in enumerate(degree):
        if res[v]:
            print("IMPOSSIBLE")
            break
        res[v] = i
    else:
        print(*res)

 

풀이

---

일반적인 위상정렬에서 순서를 바꿔주는 행위가 들어간 문제이다.

 

일반적인 위상정렬이라 함은 '순서가 정해져 있는 작업'을 수행할 때 선순위 작업을 먼저 진행하고 후순위 작업을 먼저 진행할 수 있도록 하는 알고리즘이다.

작업들의 순위를 degree로 표현하여 degree 오름차순으로 정답을 출력하면 된다.

 

하지만 이번 문제에서는 작년도 순위가 주어지고 작년도 순위에서 순위가 바뀌는 작업을 수행해야 한다.

이 때, a,b가 입력으로 주어지는데 작년도 a의 순위가 b의 순위보다 높았다면(선순위였다면) a와b의 순위가 바뀐 것이므로 a의 올해 순위는 +1, b의 올해 순위는 -1을 해준다.

여기서 a와 b가 어느 순위로 가게 될 지 모르는데 +1, -1만 해줄 수 있는 이유는 어찌되었든 작년과 순위가 바뀌었다면 순위가 바뀐 모든 짝이 m번의 입력안에서 a,b로 주어질 것이기 때문이다.

 

만약 모든 입력 a,b에 대해서 순위 교환이 이루어졌는데 순위가 같은 값들이 존재한다면 그 케이스는 정답을 정할 수 없는 케이스이므로 "IMPOSSIBLE"을 출력한다.