프로그래머스 : 순위

https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

해결 방법 : Floyd–Warshall

• 주어진 results에 따라 A 선수가 B 선수까지 도달 할 수 있다면, A 선수가 B선수를 이긴 것으로 일반화 할 수 있다.
  • Floyd Warshall을 사용하여 연결 여부만 판단한다. 
  • 산출물은 winner_table. (if w_table[A][B] = 1, then A가 B를 이긴다)
• winner_table을 Transpose하여 loser_table을 만든다.
• 자신이 이긴 선수들 + 자신이 진 선수들의 값이 n - 1이면 해당 선수의 순위를 알 수 있으므로, 
  • sum(w_table[x]) + sum(l_table[x]) == n - 1 인 x의 개수를 반환

def solution(n, results):
    
    w_table = [[0] * (n + 1) for _ in range(n + 1)] # winner table
    
    for winner, loser in results:
        w_table[winner][loser] = 1
    
    for p in range(1, n + 1): # Floyd Warshall
        for f in range(1, n + 1):
            for t in range(1, n + 1):
                if w_table[f][p] == 0 or w_table[p][t] == 0: # 연결 불가능
                    continue
                w_table[f][t] = 1 # 연결
                
    l_table = [[w_table[col][row] for col in range(n + 1)] for row in range(n + 1)] # loser table
    result = [sum(w) + sum(l) for w, l in zip(w_table, l_table)] # 이긴 선수 + 진 선수
    
    return result.count(n-1)