[Python] 프로그래머스 / 순위

문제 링크

 

여기서 Floyd-Warshall이?

갑자기 웬 플로이드-워셜인가 싶을 것이지만, 이 문제를 찬찬히 살펴보면 알게 될 것이다. Floyd-Warshall 알고리즘의 본질은, i-j의 관계를 모르더라도 i-k, k-j 사이의 관계를 알면 결국 i-j 사이의 관계를 알게 된다는 것이다. 그러므로 이 알고리즘은 비단 "거리"나 "cost"에 한정된 아이디어가 아니다. 예를들어 이는 부등호 관계에서도 성립되는 아이디어이다. i > k, k > j 를 알고 있다면, i > j 또한 알 수 있게 되기 때문이다.

 

정답 코드

def solution(n, results):
    
    graph = [[0] * n for _ in range(n)]
    
    for A, B in results :
        A -= 1
        B -= 1
        graph[A][B] = 1
        graph[B][A] = -1
        
    for k in range(n) :
        for i in range(n) :
            for j in range(n) :
                if graph[i][j] == 0 and graph[i][k] != 0 and graph[i][k] == graph[k][j] :
                    graph[i][j] = graph[i][k]
                    
    for i in range(n) :
        graph[i][i] = 1
        
    answer = 0
    for relationship in graph :
        if all(relationship) :
            answer += 1
            
    return answer