프로그래머스(programmers) 순위 python 정답[Graph, 플로이드와샬]

프로그래머스(programmers) 순위 python 정답[Graph, 플로이드와샬 알고리즘]

문제 링크

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

프로그래머스

문제 정답

def solution(n, results):
    dist_graph = [[0]*n for _ in range(n)]
    # 그래프 연결
    for w, l in results :
        dist_graph[w-1][l-1] =1
    # 플로이드 와샬
    for k in range(n):
        for w in range(n):
            for l in range(n):
            	# 진 플로이드 와샬
            	# dist_graph[w][l] = min(dist_graph[w][l], dist_graph[w][k] +  dist_graph[k][l])
                if dist_graph[w][l]== 0 and dist_graph[w][k] !=0 and dist_graph[k][l] !=0:
                    dist_graph[w][l] = 1
                
    winner_list = [0] * n
    loser_list = [0] * n
    # l열의 1 합 : l이 진 멤버 수
    # w행의 1 합 : w가 이긴 멤버 수
    for w in range(n):
        for l in range(n):
            loser_list[l] += dist_graph[w][l]
            winner_list[w] += dist_graph[w][l]    
    answer = 0
    # 특정 멤버를 이긴 사람 수 + 진 사람 수가 n-1면 순위를 결정할 수 있다.
    for index in range(n):
        if winner_list[index] + loser_list[index] == n-1:
            answer+=1

                                
    return answer

플로이드 와샬 알고리즘을 응용한다.

 

플로이드 와샬 알고리즘은 다익스트라 알고리즘이랑 유사한데,

큐를 사용하는 다익스트라와 다르게,

2차원 배열을 활용하여, 각 점(i,j)을 중간점(k)을 거쳐 이동한 거리의 최소값을 계산한다.

이 문제의 경우는, 최소 거리를 계산하는 대신, 연결되었으면 강제로 1로 표시해서 승패 판단 가능 여부를 나타낸다.

• A[i][j]가 1이면 i 관점에선 이긴거고 j 관점에선 진거다.

순위를 판단하려면, n 선수중에 n-1명과의 승패 여부를 추론할 수 있어야 한다.

플로이드 와샬로 초기화 하면 아래와 같은 배열이 나온다.

[0, 1, 0, 0, 1]
[0, 0, 0, 0, 1]
[0, 1, 0, 0, 1]
[0, 1, 1, 0, 1]
[0, 0, 0, 0, 0]

각 행의 1의 갯수는 다음을 의미한다.

• > 행의 1 갯수(합) : 이긴 멤버 수
• ^ 열의 1 갯수(합) : 진 멤버 수

따라서 행합 +열합이 n-1이면, 순위 판단이 가능하다.

 

주어진 정보로 n 선수의 유추 가능한 모든 승패 결과를 1로 표시히면,

5(idx=4)번 선수는 아무에게도 이기지 못했으며, 4명와 승부 시 패배핸다는 것을 알 수 있다.

따라서 5번 선수는 5위이다.

 

또한 2번(idx=1) 선수는 5위한테만 이기며, 1,3,4와 승부 결과 패배함을 알 수 있다.

따라서 2번 선수는 4위이다.

 

이를 winner_list(행합), loser_list(열합)으로 계산하여, index를 이용해 합이 n-1인지 체크하면, 해당 선수의 순위를 알 수 있다.