[python] 프로그래머스 - 순위

출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

# n명의 권투 선수들은 1부터 n까지 번호를 가짐
# results는 경기 결과 배열
    # 경기 결과 A B는 A가 B를 이겼음을 표시
# 순위를 매기려 하는데 몇몇 경기 결과 분실

# 알고있는 경기 결과를 통해 순위를 확실히 알 수 있는 선수의 수를 return

 

---

 

풀이

 

def solution(n, results):
    answer = 0
    INF = float('inf')
    # 모든 노드에 대해 각 노드가 다른 모든 노드를 방문 가능한가? -> 플로이드 워셜
    
    ad_matrix = [[INF for _ in range(n)] for _ in range(n)]
    
    # 그래프 초기화
    for winner, loser in results:
        ad_matrix[winner - 1][loser - 1] = 1
    
    for k in range(n): # 경유지 선정
        for i in range(n):
            if i == k:
                continue
                
            for j in range(n):
                if i == j or j == k:
                    continue
                    
                ad_matrix[i][j] = min(ad_matrix[i][j], ad_matrix[i][k] + ad_matrix[k][j])
                
    # 이긴사람 + 진사람 == n - 1
    
    row_count = [sum([1 if line[i] != INF else 0 for i in range(n)]) for line in ad_matrix]
    col_count = [sum([1 if line[i] != INF else 0 for i in range(n)]) for line in zip(*ad_matrix)]
    
    for i in range(n):
        if row_count[i] + col_count[i] == n - 1:
            answer += 1
                
    return answer

---

시간 복잡도

O(n^3)

 

Github