[프로그래머스] 순위 - python (플로이드-워셜)

순위

문제 설명

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

풀이

문제의 의도는 플로이드 워셜 알고리즘을 사용하는 것이다.

경기 결과를 진 선수가 이긴 선수를 가리키는 방향 그래프로 나타낼 수 있기 때문에 최단 거리 알고리즘을 수행할 수 있게 된다.

A와 B의 경기 결과를 확인할 때, A에서 B로 도달 가능하거나 B에서 A로 도달 가능하면 결과를 확인할 수 있다.

즉 정확하게 순위를 매기기 위해서는 자신을 제외한 모든 노드에 도달 가능해야한다. 선수의 수가 100명이므로 O(N^3)인 플로이드 워셜 알고리즘을 사용할 수 있다.

일반적인 플로이드-워셜 알고리즘은 간선 정보를 무한으로 초기화하고 도달 가능한 거리 중 최소값으로 업데이트해야하지만 이겼을 때와 졌을 때를 모두 표시해야하므로 조금 바꿔야한다.

• 이겼을 때 : 1로 표시
• 졌을 때 : -1로 표시
• 모를 때 : 0으로 표시

로 그래프를 초기화해주고 점화식에 따라 플로이드 워셜 알고리즘을 수행한다.

graph [i] [j]의 결과를 모를 경우

• 만약 i가 k를 이기고 k가 j를 이겼다면 i는 j도 이긴다. (graph [i] [j] = 1])
• 만약 i가 k한테 지고 k가 j한테 졌다면 i는 j한테도 진다. (graph [i] [j] = -1)

모두 완료 후 0의 개수가 1개인 행의 갯수를 리턴해주면 된다.

(자기 자신 제외)

def solution(n, results):
    answer = 0
    graph = [[0] * (n + 1) for _ in range(n + 1)]
    
    for a, b in results:
        graph[a][b] = 1
        graph[b][a] = -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] == 1:
                        graph[i][j] = 1
                    elif graph[i][k] == graph[k][j] == -1:
                        graph[i][j] = -1
                        
    for i in range(1, n + 1):
        if graph[i][1:].count(0) == 1:
            answer += 1
    return answer