백준 3665번: 최종 순위 (Python)

접근

위상 정렬 문제였고, 처음에 많이 헤메었지만 바뀐 순위들만 생각하는 것이 아니라 처음에 주어진 순위를 모두 어떤 처리를 해서 같이 계산해주어야 된다고 생각의 방향을 바꾸고 나서는 쉽게 해결이 되었다.

위상 정렬 기본 문제: 2021.06.20 - [코딩/백준 (Python)] - 백준 2252번: 줄 세우기 (Python)

백준 2252번: 줄 세우기 (Python)

1 2 3 4 5 다섯개의 팀이 각각 1 2 3 4 5 의 순위를 가지고 있을 때,
1 -> 2
2 -> 3
3 -> 4
4 -> 5
4개의 간선만 있다고 생각하는 것이 아니라
1 -> 3
1 -> 4
1 -> 5
2 -> 4
2 -> 5
3 -> 5
의 간선도 같이 그려주었다.

모든 간선을 더해주고 각각 in_degree를 계산해주면

team	1	2	3	4	5
간선	[2, 3, 4, 5]	[3, 4, 5]	[4, 5]	[5]	[]
in_degree	0	1	2	3	4

와 같은 초기값을 얻을 수 있다.

이후 입력받는 순위 변동 팀들을 계산하여 기존에 높은 순위 팀의 tree 에서 낮은 순위의 팀을 빼고, in_degree 를 1 더해준다.
기존 낮은 순위 팀의 tree 에 높은 순위의 팀을 더하고, in_degree 를 1 빼준다.

모든 입력을 받고 난 후, 위상 정렬 q 계산을 진행해주게 된다.

이 때, in_degree 값에 0 이 없거나, 진행 중 q 의 원소 수가 2개 이상이거나, in_degree 값이 0 이하로 내려간다면 순위를 정상적으로 구할 수 없으므로 'IMPOSSIBLE'을 출력해준다.

코드

import sys
from collections import deque

c = int(sys.stdin.readline())
for __ in range(c):
    n = int(sys.stdin.readline())
    ranking = list(map(int, sys.stdin.readline().split()))

    q = deque()
    tree = [[] for _ in range(n + 1)]
    in_degree = [0] * (n + 1)

    for i in range(0, n - 1):
        for j in range(i + 1, n):
            tree[ranking[i]].append(ranking[j])
            in_degree[ranking[j]] += 1

    m = int(sys.stdin.readline())
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        check = True
        for i in tree[a]:
            if i == b:
                tree[a].remove(b)
                tree[b].append(a)
                in_degree[b] -= 1
                in_degree[a] += 1
                check = False
        if check:
            tree[b].remove(a)
            tree[a].append(b)
            in_degree[a] -= 1
            in_degree[b] += 1

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

    result = True
    result_list = []
    if not q:
        result = False
    while q:
        if len(q) > 1:
            result = False
            break
        now = q.popleft()
        result_list.append(now)
        for i in tree[now]:
            in_degree[i] -= 1
            if in_degree[i] == 0:
                q.append(i)
            elif in_degree[i] < 0:
                result = False
                break

    if not result or len(result_list) < n:
        print('IMPOSSIBLE')
    else:
        print(*result_list)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!