프로그래머스: 순위

Floyd-Warshall 알고리즘을 사용한다.

https://focalpoint.tistory.com/6

최단 거리 알고리즘

def solution(n, results):
    graph = [[0] * (n+1) for _ in range(n+1)]
    for result in results:
        w, l = result
        graph[w][l] = 1
        graph[l][w] = -1
    
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if graph[i][j] == 0:
                    if graph[i][k] == graph[k][j]:
                        graph[i][j] = graph[i][k]
    
    answer = 0
    for i in range(1, n+1):
        c = 0
        for j in range(1, n+1):
            if graph[i][j] != 0:
                c += 1
        if c == n - 1:
            answer += 1
    return answer