[ Lv 3 ] 순위

문제 설명

---

---

풀이 과정

---

1. 플로이드 알고리즘을 통해 승리, 패배 시 가능한 최단 경로들을 모두 구해준다.

 

2. 각 선수의 케이스에서 승리해서 도달 가능한 선수의 수 + 패배해서 도달 가능한 선수의 수가 전체 선수의 수와 같다면 순위 지정이 가능하다.

 

3. 케이스의 수를 모두 세서 리턴해주면 된다.

 

---

def solution(n, results):
    answer = 0
    
    INT_MAX = int(10e9)
    win_matrix = [[INT_MAX] * (n+1) for _ in range(n+1)]
    lose_matrix = [[INT_MAX] * (n+1) for _ in range(n+1)]
    
    for i in range(n+1):
        win_matrix[i][i] = 0
        lose_matrix[i][i] = 0
    
    for src, dest in results:
        win_matrix[src][dest] = 1
        lose_matrix[dest][src] = 1
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                win_matrix[j][k] = min(win_matrix[j][k], win_matrix[j][i] + win_matrix[i][k])
                lose_matrix[j][k] = min(lose_matrix[j][k], lose_matrix[j][i] +
                                       lose_matrix[i][k])
    
    for i in range(1, n+1):
        count = len([k for k in win_matrix[i] if k != INT_MAX]) + len(
            [k for k in lose_matrix[i] if k != INT_MAX])
        if count == n+1:
            answer += 1
        
    
    
    return answer