[백준3665번] 최종 순위 / Python3

문제

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

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

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

입력

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

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

출력

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

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

예제 입력 1

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

예제 출력 1

5 3 2 4 1
2 3 1
IMPOSSIBLE

나의 풀이

위상정렬을 인접 리스트로만 접근을 했던 나에게 새로운 깨달음을 준 문제였다.

우선 작년의 순위와 순위의 바뀐 정보를 주었기 때문에 순위를 정할 수 없는 경우는 있지만, 확실한 순위를 찾을 수 없는 경우는 없다고 생각할 수 있다. 따라서, 이 문제에서는 위상 정렬을 할 수 있는지 없는지를 체크하는 문제라고 볼 수도 있었다. 다시말해, 그래프를 그리고 사이클이 존재하는지 안하는지를 찾는 것이라고 할 수도 있다.

이 문제를 풀기위해서는 2차원 배열이 필요하다. n명이라면 n*n의 배열을 만들고 각 팀에 따라 앞에 오는 팀들에 대한 정보를 가져야한다. 문제에서 주어진 예제를 예로들면 다음과 같다.

  1 2 3 4 5 
1 F F F F F
2 T F F F F
3 T T F F F
4 T T T F F
5 T T T T F

-- 순위 변동 후--

  1 2 3 4 5 
1 F F F F F
2 T F F T F
3 T T F T F
4 T F F F F
5 T T T T F

간단히 설명하자면 2번 팀의 경우 원래는 1번 팀보다만 앞에 존재하기 때문에 [2][1]만 T이지만 2번과 4번의 순위가 변경되었다는 정보를 가지고 변경하면 [2][4]는 T가 되고 [4][2]는 T에서 F로 바뀌게 된다.

또한, 각 행의 합을 각 팀의 진입차수로 볼 수 있다. 그렇기 때문에 진입 차수가 0인 것부터 큐에 넣고 [i][진입차수가 0인 팀의 번호]로 앞에 있는 팀(T)인 팀에 진입 차수를 감소시켜나가면서 진입 차수가 0이 되는 것을 리스트에 추가를 하면서 순위를 찾을 수 있다.

만약, 위의 과정을 거치면서 아직 모든 팀이 순위가 메겨지지 않았지만 진입차수가 0인 것이 존재하지 않을 수 있다. 예로는 위의 상황에서 4번 팀과 5번 팀이 바뀌는 것을 추가해보면 된다. 즉, 이러한 경우가 순위를 정할 수 없는 경우이다. 따라서, 필자는 위상정렬 알고리즘이 끝난 뒤 최종 순위를 담는 배열의 길이가 n이 아니라면 불가능한 경우로 판단하였다.

코드

# 3665번 최종 순위
from sys import stdin
from collections import deque


for _ in range(int(stdin.readline())):
    n = int(stdin.readline())
    rank = list(map(int, stdin.readline().split()))
    rank_info = [[False] * (n+1) for _ in range(n+1)]
    in_degree = [0] * (n+1)

    for i in range(n):
        for j in range(i+1, n):
            # i번째가 j번째보다 앞에 있음을 체크
            rank_info[rank[i]][rank[j]] = True

    m = int(stdin.readline())
    for _ in range(m):
        a, b = map(int, stdin.readline().split())

        # 순위에 변동이 있다면 두 개의 값을 변경
        rank_info[a][b], rank_info[b][a] = rank_info[b][a], rank_info[a][b]

    final_rank = []     # 최종 순위를 저장
    q = deque()
    for i in range(1, n+1):
        in_degree[i] = rank_info[i].count(True)     # 진입차수를 계산
        if in_degree[i] == 0:
            q.append(i)

    # 위상정렬 알고리즘
    while q:
        cur = q.popleft()
        final_rank.append(cur)

        for i in range(1, n+1):
            if rank_info[i][cur]:
                in_degree[i] -= 1
                if in_degree[i] == 0:
                    q.append(i)

    if len(final_rank) == n:
        print(*final_rank[::-1])
    else:
        print("IMPOSSIBLE")