[Python3]프로그래머스_순위

문제출처: https://programmers.co.kr/learn/courses/30/lessons/49191

접근법

정답은 플로이드-와샬 알고리즘을 통해 구현해야 했다.
플로이드-와샬은 알고 있었지만 문제를 보고 고민하면서 생각을 못해서
풀이를 보고 이해를 했다.

• 어떤 선수의 순위를 알려면 다른 선수들과의 경기결과를 모두 알고 있어야 한다.
• 만약 1번 선수가 2번 선수를 이기고 ( [1,2] ) , 2번 선수가 3번 선수를 이긴다면 ( [2,3] ) , 우리는 쉽게 1번 선수가 3번 선수를 이긴다는 추론을 할 수 있다. ( [1,3] ) 그리고 여기서 3번 선수는 1번,2번 선수한테 진다는 사실과 2번 선수는 1번 선수한테 진다는 사실을 알 수 있다. 이를 통해 우리는 세명의 경기결과를 추론할 수 있게 된다.
• a 선수가 b선수를 이기는 경우를 1로 표시하고 지는경우 -1로 표시하여
  플로이드-와샬 알고리즘을 통해 위와 같은 추론이 가능한 관계들을 모두 체크하여 값 1 과 -1로 표시해주면 내 순위를 알 수 있는 선수들은 자신과의 경기결과를 제외하고 n-1 개의 경기결과를 알 수 있다.

코드

# 부모 노드는 자식노드들을 모두 이길 수 있다 ? 
# 부모 노드 + 자식 노드 == n-1
# 플로이드-와샬
def solution(n, results):
    answer = 0
    v = [ [0] * n for _ in range(n)  ]
    for i,j in results:
        v[i-1][j-1] = 1
        v[j-1][i-1] = -1
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if v[i][k] == v[k][j] == 1:
                    v[i][j] = 1
                    v[j][i] = v[k][i] = v[j][k] = -1
    for row in v:
        if row.count(0) == 1:
            answer += 1
    return answer