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

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

3665번: 최종 순위

문제

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

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

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

출력

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

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

 

 

---

이번에 위상 정렬(Topology Sort)에 대해 처음 배우게 되었다.

위상 정렬(Topology Sort)은 순서가 정해진 작업의 차례를 결정할 때 사용되는 알고리즘이다.

해당 알고리즘은 작업의 시작 정점을 찾아야 하기 때문에 사이클이 없는 방향 그래프 상에서만 이루어져야 한다.

 

위상 정렬은 다음의 두 가지 방법으로 구현될 수 있다.

• 진입 차수를 이용한 bfs 구현
• 진출 차수를 이용한 dfs 구현

 

※ 진입 차수(in-Degree): 어떠한 작업이 수행되기 전에 수행되어야 할 작업들의 개수

※ 진출 차수(in-Degree): 어떠한 작업이 수행된 이후에 수행되어야 할 작업들의 개수

 

 

이 중 bfs 구현 방법을 공부했다. 구현 과정은 다음과 같다.

 

1. 진입 차수가 0인 정점들을 양방향 큐에 넣는다.
2. 큐에서 원소를 꺼낸 후, 연결된 간선들을 해제한다.
3. 해제 과정에서 진입 차수가 0이 된 정점들을 큐에 넣는다.

 

 

 

<< 전체 코드 >>

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

T = int(input())
for _ in range(T):
    n = int(input())
    graph = defaultdict(list)
    indegree = [0 for _ in range(n+1)]
    score = list(map(int, input().split()))
    for i in range(n-1):
        for j in range(i+1, n):
            graph[score[i]].append(score[j])
            indegree[score[j]] += 1

    m = int(input())
    for _ in range(m):
        a, b = map(int, input().split())
        if a in graph[b]:
            graph[b].remove(a)
            indegree[a] -= 1
            graph[a].append(b)
            indegree[b] += 1
        elif b in graph[a]:
            graph[a].remove(b)
            indegree[b] -= 1
            graph[b].append(a)
            indegree[a] += 1

    q = deque()
    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)

    answer = []
    while q:
        cur = q.popleft()
        answer.append(cur)
        for v in graph[cur]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)

    if len(answer) < n:
        print('IMPOSSIBLE')
    else:
        print(*answer)