[이것이 코딩테스트다] 최종 순위🥵

🗃️문제 설명

올해 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) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.

🖥️코드

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

T = int(input())
for _ in range(T):
    n = int(input())
    indegree = [0] * (n + 1)                            # 진입 차수 배열
    graph = [[False] * (n + 1) for _ in range(n + 1)]   # 인접 행렬
    rank = list(map(int, input().split()))

    for i in range(n):
        for j in range(i + 1, n):
            graph[rank[i]][rank[j]] = True  # 연결 정보 True
            indegree[rank[j]] += 1          # i가 j보다 순위가 높은 것이므로
    
    m = int(input())
    for _ in range(m):
        a, b = map(int, input().split())    # 순위가 바뀐 팀
        if graph[a][b]:
            graph[a][b] = False
            graph[b][a] = True
            indegree[a] += 1    # b팀의 순위가 높아지게 되면 a팀 입장에서 보았을 때 앞쪽에 한 팀이 자리잡게 되므로 진입 차수 배열을 +1
            indegree[b] -= 1    # a팀의 순위가 낮아지게 되면 b팀 입장에서 보았을 때 뒤쪽에 한 팀이 자리잡게 되므로 진입 차수 배열을 -1
        else:
            graph[a][b] = True
            graph[b][a] = False
            indegree[b] += 1
            indegree[a] -= 1
    
    result = []
    q = deque()
    # 진입 차수 값이 0이면 먼저 넣기
    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)

    # 인원 수만큼 돌렸는데 그 전에 진입 차수가 비어있게 된다면? → 사이클이 존재함
    # 또한 큐의 원소가 두 개 이상이라면? → 위상 정렬의 결과가 여러 가지가 나올 수 있음
    cycle = False
    flag = False
    
    for i in range(n):
        if len(q) == 0:
            cycle = True
            break
    
        if len(q) >= 2:
            flag = True
            break

        v = q.popleft()
        result.append(v)
        for j in range(1, n+1):
            if graph[v][j]:
                indegree[j] -= 1
                if indegree[j] == 0:
                    q.append(j)

    if cycle:   # 사이클이 발생한다면?
        print("IMPOSSIBLE")
    elif flag:  # 확실한 순위를 찾을 수 없다면?
        print("?")
    else:
        for i in result:
            print(i, end=" ")
        print()

🧠아이디어

알고리즘 유형 : 위상 정렬

위상 정렬(topology sort)

• 정의 : 위상 정렬이란 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
• 노드 간의 순서를 결정하며 이 때, 사이클이 없어야 한다.
• 위상 정렬의 시간 복잡도는 O(V + E)이다.
• 위상 정렬에서는 항상 유일한 값으로 정렬이 되지 않는다.
• 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없게 된다.

위상 정렬의 핵심 이론 - 진입 차수

• 진입 차수란 자기 자신을 가리키는 간선의 개수를 말한다.
• 진입 차수가 0이라는 것은 자신의 앞에 오는 노드가 존재하지 않는다는 것을 말한다.

🔒문제 출처 및 참고 코드

이것이 코딩테스트다 with 파이썬 - 최종순위
모범 답안 - 최종순위