프로그래머스 순위

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

처음에 문제 이해에 어려움이 있었다.
문제의 핵심은 승패를 그래프상으로 나타내였을때 다른 노드를 타고 연결이 가능하여 모든 노드를 순회할 수 있는지 알아보는 것이었다.
그래프 순회에는 플로이드워셜 알고리즘의 로직을 사용할 수 있다.
다익스트라 알고리즘이 한 정점에서 다른 정점까지 최단거리를 구하는 것이었다면,
플로이드 워셜 알고리즘은 모든 정점에서 모든 정점까지의 최단거리를 구할 수 있다.

플로이드 워셜 알고리즘을 이용해 삼중for문으로 해결할 수 있다.

def solution(n, results):
    answer = 0
    graph = [[0]*(n+1) for i in range(n+1)]
    for r in results:
        graph[r[0]][r[1]] = 1
        graph[r[1]][r[0]] = -1
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if graph[i][j] == 0:
                    if graph[i][k] == 1 and graph[k][j] == 1:
                        graph[i][j] = 1
                    elif graph[i][k] == -1 and graph[k][j] == -1:
                        graph[i][j] = -1
    for i,row in enumerate(graph):
        if row[i] == 0 and row.count(0) == 2:
            answer += 1
                                  
    return answer