[백준 3655] 최종 순위 - Python

문제 보기

[사용한 알고리즘]

위상 정렬(Topological)

 

[문제 접근]

순서를 나열하는 문제는 위상 정렬을 활용하면 효과적으로 구현할 수 있습니다.

 

[알고리즘]

1. 작년 순위 정보를 통해 2차원 graph 배열과 1차원 indegree 배열 값을 할당합니다.

 - graph[i][j]: i보다 j가 순위가 낮으면 True, 반대는 False를 대입합니다.

 - indegree [i]: i보다 순위가 낮은 팀의 개수를 대입합니다.

2. 순위 변동이 있는 팀은 graph 값과 indegree 값을 업데이트합니다.

3. 위상 정렬을 수행합니다.

 - 사이클이 있으면 IMPOSSIBLE을 리턴합니다. (시작점을 찾지 못합니다)

 - 큐에 값이 2개 이상 있으면 ?를 리턴합니다. (여러 가지 경우의 수가 나올 수 있습니다)

 - 이외의 경우는 순위를 리턴합니다. 

 

[코드]

import sys
from collections import deque


def topological():
    q = deque()
    # 진입 차수가 0인 값 q에 삽입
    for i in range(1, n + 1):
        if indegree[i] == 0:
            q.append(i)

    # 위상 정렬
    result = []
    for i in range(1, n + 1):
        if len(q) == 0:  # 사이클이 있는 경우(시작점을 찾지 못한다)
            return "IMPOSSIBLE"
        index = q.popleft()
        result.append(index)
        for j in range(1, n + 1):
            if graph[index][j]:  # index와 연결되어 있다면
                indegree[j] -= 1  # 진입 차수 감소
                if indegree[j] == 0:
                    q.append(j)
                    if len(q) >= 2:  # 결과가 2개 이상 가능한 경우(일관성이 없는 정보)
                        return "?"

    return " ".join(map(str, result))


if __name__ == "__main__":
    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        rank = list(map(int, sys.stdin.readline().split()))  # 작년 순위
        graph = [[False] * (n + 1) for _ in range(n + 1)]
        m = int(sys.stdin.readline())  # 순위 변동 수

        # 진입 차수
        indegree = [0] * (n + 1)

        # 자신보다 순위가 낮은값으로 연결 (1등 -> 2등 ... -> n등)
        for i in range(n):
            for j in range(i + 1, n):
                graph[rank[i]][rank[j]] = True
                indegree[rank[j]] += 1

        # 순위 변동
        for _ in range(m):
            a, b = map(int, sys.stdin.readline().split())
            if not graph[a][b]:
                graph[b][a] = False
                indegree[b] += 1
                graph[a][b] = True
                indegree[a] -= 1
            else:
                graph[b][a] = True
                indegree[b] -= 1
                graph[a][b] = False
                indegree[a] += 1

        # 출력
        answer = topological()
        print(answer)