[🥇1 / 백준 3665 / 파이썬] 최종 순위

 

3665번: 최종 순위

 

문제

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.

올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.

창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.

입력

첫째 줄에는 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500)
• n개의 정수 t_i를 포함하고 있는 한 줄. (1 ≤ t_i ≤ n) t_i는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 t_i는 서로 다르다.
• 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000)
• 두 정수 a_i와 b_i를 포함하고 있는 m줄. (1 ≤ a_i < b_i ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.

출력

각 테스트 케이스에 대해서 다음을 출력한다.

• n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

 

예제 입력  3 5 5 4 3 2 1 2 2 4 3 4 3 2 3 1 0 4 1 2 3 4 3 1 2 3 4 2 3

예제 출력  5 3 2 4 1 2 3 1 IMPOSSIBLE

 

풀이

 

위상 정렬을 통해 상대적 순위 변동을 계산하여 확실한 한 순위를 찾는 문제이다.

위상 정렬을 위한 간선이 주어지지 않기 때문에 직접 간선을 만든 뒤, 알맞게 조정하고 위상 정렬을 수행해야 한다.

 

예제 1을 예로 들자면, 처음에 순위가 주어지기 때문에 간선이 5 → 4 → 3 → 2 → 1 이라고 생각하기 쉽다.

하지만 5는 4에 대해서만 앞서는 것이 아니라, 다른 모든 정점에 대해 앞선다.

 

즉,

5 → 4, 3, 2, 1

4 → 3, 2, 1

3 → 2, 1

2 → 1

과 같은 간선이 만들어진다.

이렇게 작년의 순위로 위와 같은 선작업을 진행해준다.

 

 

이제 순위를 뒤집는 입력을 받는다.

문제에서 아래와 같이 말했다.

 

예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.

 

여기서 헷갈릴 수 있는 것이, (6, 13) 을 발표했다고 앞에 6이 13보다 더 높다는 의미가 아니다.

그냥 (6, 13) 이든 (13, 6) 이든 두 팀의 순위가 역전 관계에 놓였다고 말하는 것일 뿐이다.

다시 말하지만 순서는 아무 의미 없다.

 

해당 사항 반례

 

반례 입력  1 2 1 2 1 1 2

반례 출력  2 1

 

아무튼 이제 순위를 뒤집어야 한다.

입력이 들어온다면, 두 정점의 간선을 배열에 찾아서 방향을 바꿔주도록 하자.

진입 차수를 계산하는 배열도 가감하는 것을 잊지 말아야 한다.

 

 

이제 마지막으로, 위상 정렬을 진행해주면 된다.

만약 시작 노드가 없거나 위상 정렬을 끝냈는 데도 방문하지 않은 정점이 있다면, 즉 사이클이 존재한다면 IMPOSSIBLE을 출력하자.

 

문제에서 확실한 순위를 찾을 수 없다면 "?"를 출력하라고 했지만 이미 작년에 확실한 순위가 주어졌기 때문에 해당 예외는 없다.

확실한 순위가 있거나, 데이터의 일관성이 존재하지 않는 사이클 형태 둘 중 하나만 있을 뿐이다.

 

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    # 작년 순위
    n = int(input())
    rank = list(map(int,input().split()))
    cntLink = [-1] + [0]*n
    link = [[] for _ in range(n+1)]
    for i in range(n):
        link[rank[i]] = rank[i+1:]
        cntLink[rank[i]] = i
    
    # 순위 역전
    for _ in range(int(input())):
        a,b = map(int,input().split())
        if a in link[b]:
            link[b].remove(a)
            link[a].append(b)
            cntLink[a] -= 1
            cntLink[b] += 1
        else:
            link[a].remove(b)
            link[b].append(a)
            cntLink[b] -= 1
            cntLink[a] += 1
            
    # 시작 노드
    q = deque()
    for i in range(1,n+1):
        if not cntLink[i]:
            q.append(i)
    if not q:
        # 시작 노드 부재, 사이클
        print("IMPOSSIBLE")
        continue
    
    # 위상 정렬
    ans = []
    while q:
        v = q.popleft()
        ans.append(v)
        for i in link[v]:
            cntLink[i] -= 1
            if not cntLink[i]:
                q.append(i)
    if sum(cntLink) > -1:
        # 사이클 존재
        print("IMPOSSIBLE")
    else:
        print(*ans)