[프로그래머스] - 순위 [파이썬][플로이드 와셜]

문제를 보고 고민하다가 뭔가 순환이 없기도 하고, 방향을 뚜렷하고, 가중치도 없겠다해서 위상정렬로 풀려고 했지만,
어디서 핀트가 나간건지 끝내 못풀고 결국 플로이드 와셜을 사용해야 한다는 힌트를 얻은 문제

 

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

프로그래머스

 

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.
•  

문제를 보고 고민하다가 뭔가 순환이 없기도 하고, 방향을 뚜렷하고, 가중치도 없겠다해서 위상정렬로 풀려고 했지만,
어디서 핀트가 나간건지 끝내 못풀고 결국 플로이드 와셜을 사용해야 한다는 힌트를 얻은 문제

---

해설

하나의 노드가 다른 모든 노드와의 관계를 알아야 한다는 것을 먼저 깨달아야 풀 수 있는 문제이다. 
이런 관계에 대해서 적합한 알고리즘이 플로이드 와샬 알고리즘이다.
예를 들어 [[1,5],[5,6]]이라는 변수가 주어 졌을때 우리는 1 -> 6( 1이 6을 이겼다)라는 것을 알고 변수에 주어지지 않은 1과6의 관계를 떠올릴 수 있게 된다.

즉 이번 문제는 저런 연결고리들을 계속해서 연결해 나아가는 문제인 것이다.

플로이드 와셜을 무조건 최단 거리 관련 문제와 연결시켜 생각했는데, 모든 노드와 모든 노드와의 관계를 계산한다는 것이 플로이드 와셜의 근본적인 개념인 것 같다.

 

def solution(n, results):
    graph = [[0] * (n) for _ in range(n)]

    for A,B in results:
        graph[A - 1][B - 1] = 1
        graph[B - 1][A - 1] = -1


    for i in range(n): #중간노드
        for j in range(n):#시작 노드
            for k in range(n):# 종점 노드
                if graph[j][k] != 0: #이미 결과가 정해져 있음
                    continue
                if graph[j][i] == 1 and graph[i][k] == 1: # j 가 i를 이기고 i가 k를 이겼으니 j 가 k를 이긴거나 마찬가지
                    graph[j][k] = 1
                elif graph[j][i] == -1 and graph[i][k] == -1: #위와 반대의 상황
                    graph[j][k] = -1

    # [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]에 대한 그래프
    # 순위를 정할때 당연히 "나"이외의 모든 노드들과 관계를 갖고 있어야 한다.
    # [0,   1,   0,  0, 1]
    # [-1,  0,  -1, -1, 1] -> 순위 확정
    # [0,   1,   0, -1, 1]
    # [0,   1,   1,  0, 1]
    # [-1, -1,  -1, -1, 0] -> 순위 확정
    answer = 0
    for g in graph:
        if len(list(filter(lambda x: x != 0,g))) == n - 1:
            answer += 1

    return answer