(Python) 프로그래머스 - 순위

01 Mar 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

def solution(n, results):
    answer = 0
    INF = int(1e9)
    graph = [[INF] * n for _ in range(n)]

    for i in range(n):
        graph[i][i] = 0

    for a, b in results:
        graph[a - 1][b - 1] = 1

    floyd(graph, n)

    for i in range(n):
        key = 1
        for j in range(n):
            if graph[i][j] == INF and graph[j][i] == INF:
                key = 0
                break

        if key:
            answer += 1

    return answer


def floyd(graph, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

순위를 정하는 알고리즘은 위상정렬 알고리즘이다. 하지만 위상정렬 알고리즘은 모든 순위가 정확히 나올 때 사용하는 알고리즘이다.
순위가 중간에 빠진 경우 해당 위치에서 자신을 제외한 모든 곳으로 이동할 수 있어야 순위를 정할 수 있다.
이는 플로이드 워셜 알고리즘으로 해결할 수 있다.