[백준] 3665번 최종 순위 (by Python)

문제

www.acmicpc.net/problem/3665

3665번: 최종 순위

 

풀이

위상 정렬(Topology Sort)를 사용하는 문제이다. 주어진 올해 순위를 순위가 낮은 팀이 높은 팀을 가리키는 유향 그래프로 나타내었다. 원래는 위상 정렬에 쓰이는 그래프는 인접 리스트로 구현하였는데, 이번에는 방향성이 유동적이므로 이를 잘 다루기 위해 인접 행렬로 구현했다. 

바뀐 순위들에 대해서 edge의 방향을 바꾸어주고 이에 대해 위상 정렬을 시행해주면 된다. 다만 주어지는 정보에 모순이 있거나 정보가 부족해 사이클이 발생하는 경우에 "IMPOSSIBLE"을, 그리고 같은 진입 차수에 있어 순서를 구분할 수 없는 경우에 "?"를 프린트해주면 된다.

from collections import deque

t = int(input())
for _ in range(t):
    n = int(input())
    rank = list(map(int, input().split()))
    graph = [[False] * (n + 1) for _ in range(n + 1)]
    indegree = [0] * (n + 1)
    for i in range(n):
        for j in range(i + 1, n):
            graph[rank[j]][rank[i]] = True
            indegree[rank[i]] += 1
    m = int(input())
    for _ in range(m):
        a, b = map(int, input().split())
        if not graph[a][b]:
            a, b = b, a
        graph[a][b], graph[b][a] = False, True
        indegree[a] += 1
        indegree[b] -= 1
    q = deque()
    answer = []
    count = 0
    for i in range(1, n + 1):
        if indegree[i] == 0:
            count += 1
            q.append(i)
    if count != 1:
        if count > 1:
            print("?")
        elif count == 0:
            print("IMPOSSIBLE")
        continue
    while q and count == 1:
        count = 0
        now = q.popleft()
        answer.append(now)
        for i in range(1, n + 1):
            if graph[now][i]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    count += 1
                    q.append(i)
    if count > 1:
        print("?")
    elif len(answer) != n:
        print("IMPOSSIBLE")
    else:
        print(*answer[::-1])

※ 마지막에 위상 정렬이 낮은 순위 순으로 되어있으므로 거꾸로 출력하도록 해주었다.