[Python] 순위

문제 참고

프로그래머스

 

코드 작성

성공 #1

def solution(n, results):
    answer = 0
    INF = int(1e9)
    graph = [[INF] * (n + 1) for _ in range(n + 1)]
    
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if a == b:
                graph[a][b] = 0
    
    for r in results:
        graph[r[0]][r[1]] = 1
        graph[r[1]][r[0]] = -1
    
    for k in range(1, n + 1):
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                if graph[a][b] == INF:
                    if graph[a][k] + graph[k][b] == 2:
                        graph[a][b] = 1
                        graph[b][a] = -1
                    elif graph[a][k] + graph[k][b] == -2:
                        graph[a][b] = -1
                        graph[b][a] = 1
    
    for a in range(1, n + 1):
        if sum(graph[a][1:]) < 100:
            answer += 1
            
    return answer

플로이드 워셜 알고리즘을 이용하면 된다.

우선 INF(1e9)로 graph를 초기화하고, 자기 자신과의 싸움은 0으로 초기화

그리고 results에 따라 이긴 선수는 1, 진 선수는 -1로 초기화한다.

graph[a][k] + graph[k][b] 라면 A 선수는 B 선수를 이길 수 있다는 것을 이용한다.

이 알고리즘을 실행하면 아래와 같이 graph가 정리된다.

 

1e9	1e9	1e9	1e9	1e9	1e9
1e9	0	1	1e9	1e9	1
1e9	-1	0	-1	-1	1
1e9	1e9	1	0	-1	1
1e9	1e9	1	1	0	1
1e9	-1	-1	-1	-1	0

graph를 n + 1로 초기화했기 때문에 1열, 1행은 무시하자. (1e9로만 이루어진 부분)

 

순위가 결정될 수 있는 선수들은 1e9를 포함하지 않아야 한다.

따라서 순위가 결정되는 선수는 2번, 5번으로 2명이 된다.