[백준] 3665 최종 순위 (Python 파이썬)

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

3665번: 최종 순위

문제 설명

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

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

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

---

풀이 과정

이 문제는 일반적인 위상정렬이랑은 다르게, 간선처리 부분에 조금 신경을 써야 한다.

 

왜냐하면 둘의 상대적인 순위관계가 바뀌었을 때,

둘만의 상대적인 순위만 바뀐것이지, 그 외의 것들과는 순위관계가 바뀌지 않기 때문이다.

 

예를 들어, 5 -> 4 -> 3 -> 2 -> 1 로 순위가 주어졌을 때

(5번이 1등, 4번이 2등, 3번이 3등 ...)

5번은 4번보다 순위과 높고, 3번보다도 순위가 높은데

5번과 3번의 관계가 바뀌었다고 해서 5번이 4번보다 순위가 낮아지진 않는다.

 

그래서 각각의 원소들간의 모든 관계를 표시해야 하므로

5번은 4번,3번,2번,1번 보다도 순위가 높음을 표현하기 위해 모든 간선을 표시해야 한다.

 

이를 이용하여, 인접리스트로 그래프를 구현하게 되면

1 -> [ ]

2 -> [1]

3 -> [2, 1]

4 -> [3, 2, 1]

5 -> [4, 3, 2, 1]

으로 그래프가 형성이 되는데,

 

5번과 3번의 상대적인 순위 관계가 바뀐다면,

5번그래프에 3번을 빼주어야 하고

3번 그래프에 5를 넣어주어야 한다.

 

이 때, 3번으로 들어오는 간선이 하나 줄어들고, 5번으로 들어오는 간선이 하나 늘어났으므로

차수(indegree)도 변경을 해주어야 한다.

 

그리고, 문제에서 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다고 했는데

일관성이 없는 경우는 사이클이 발생하는 경우를 이야기한다.

 

즉, 원소들간의 관계가 잘못 표현되어 그래프에 사이클이 발생하여 위상관계를 표현할 수 없기 때문에

이 부분도 예외처리를 해주어야 한다.

예를 들어, 큐에 존재하는 원소의 개수가 2개가 된다던지, 1개도 없는 경우가 발생하는 경우이다.

직접 그림을 그려보면 알겠지만,

사이클이 발생하면 큐에 아무원소도 들어갈 수 없다.

 

또한, 한 번에 2개 이상의 원소가 들어간다는 것은

진입차수가 0인 원소가 두개 이상이 되므로 순위를 정할 수 없는 경우가 된다.

 

마지막으로, 확실한 순위를 찾을 수 없는 경우는 발생하지 않으므로 신경을 쓰지 않아도 된다.

from collections import deque
import sys

t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())

    graph = [[] for _ in range(n + 1)]
    inDegree = [0 for _ in range(n + 1)]
    queue = deque()
    answer = []
    flag = 0

    team = list(map(int, sys.stdin.readline().rstrip().split()))

    for j in range(n - 1):
        for k in range(j + 1, n):
            graph[team[j]].append(team[k])
            inDegree[team[k]] += 1

    m = int(sys.stdin.readline())
    for j in range(m):
        first, second = map(int, sys.stdin.readline().rstrip().split())
        flag = True

        for k in graph[first]:
            if k == second:
                graph[first].remove(second)
                inDegree[second] -= 1
                graph[second].append(first)
                inDegree[first] += 1
                flag = False

        if flag:
            graph[second].remove(first)
            inDegree[first] -= 1
            graph[first].append(second)
            inDegree[second] += 1

    for j in range(1, n + 1):
        if inDegree[j] == 0:
            queue.append(j)

    if not queue:
        print("IMPOSSIBLE")
        continue

    result = True
    while queue:
        if len(queue) > 1:
            result = False
            break

        tmp = queue.popleft()
        answer.append(tmp)
        for j in graph[tmp]:
            inDegree[j] -= 1
            if inDegree[j] == 0:
                queue.append(j)
            elif inDegree[j] < 0:
                result = False
                break

    if not result or len(answer) < n:
        print("IMPOSSIBLE")
    else:
        print(*answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !