프로그래머스 Level 3 순위

순위를 정확하게 매길 수 있는 사람이 몇 명인지 찾는 문제이다.

플로이드 와샬 알고리즘을 모른다면 풀기 조금 힘들 것 같은 문제이다. 

플로이드 와샬을 사용해서 최단경로가 아닌 승패를 확인해주면 된다.  

EX)

graph[0][1] = 1 -> 1가 2를 이김

graph[4][3] = -1 -> 4가 5를 이김

graph[1][2] = 0 -> 2와 3의 승패를 알 수 없음 

def solution(n, results):
    graph = [[0]*n for i in range(n)]
    for a, b in results:
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = -1
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] == 1 and graph[k][j] == 1:
                    graph[i][j] = 1
                if graph[i][k] == -1 and graph[k][j] == -1:
                    graph[i][j] = -1
    
    ans = 0
    for li in graph:
        if li.count(0) == 1:
            ans += 1
    return ans