[프로그래머스] 순위(Floyd-Warshall Algorithm)

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

코딩테스트 연습 - 순위

 

Floyd-Warshall Algorithm을 사용하는 문제입니다. 

(알고리즘에 관해서는 추후 포스팅 하겠습니다.)

 

문제부터 간단히 요약해보면, 

n명의 권투선수의 경기결과를 임의로 알려주고, 순위를 정확하게 알 수 있는 선수들의 수를 구하는 문제입니다. 

 

총 5명의 권투선수가 있고, 4번선수가 3번선수를 이기고, 4번선수가 2번선수를 이기고, ...의 예시입니다. 

 

이 때 2번선수와 5번 선수의 순위만 정확하게 알 수 있다는 것을 알 수 있고, 2를 return하는 것이 목표인 문제입니다. 

 

즉

solution(n, results)에

n : 선수의 수

results : 경기 결과를 담은 2차원 배열

이 input으로 들어갈 때

 

순위를 정확하게 알 수 있는 선수의 수를 return해야 합니다. 

 

<Solution>

기존의 알려진 Floyd-Warshall Algorithm을 변형하여 풀어봅시다. 

 

return 해야하는 선수의 수는 선수들에 대한 경기 결과를 n-1개 알 수 있다면 그 선수의 순위를 정확하게 파악이 가능하다는 이야기가 된다는 아이디어에서 출발하겠습니다. 

 

간단한 예시로 알고리즘을 설명하겠습니다. 

다음과 같은 그래프 상태가 있다고 가정하면, 

solution(5, [[4,5],[5,3],[3,1],[1,2]]) 의 상태

 

목표는 4번 선수가 5,3,1,2 선수를 모두 이긴다는 정보를 알게 하여야 합니다. 

 

 

 

 

 

 

 

현재의 그래프의 상태를 2D array에 표현하면 

선수 1 [0, 1, 0, 0, 0]
선수 2 [0, 0, 0, 0, 0]
선수 3 [1, 0, 0, 0, 0]
선수 4 [0, 0, 0, 0, 1] (4가 5를 이김)
선수 5 [0, 0, 1, 0, 0]

와 같은 상태가 됩니다. 

 

이 그래프를 Floyd-Warshall Algorithm을 적용하는데 아래와 같이 적용을 하게 되면, 매번 순회하면서 k번 선수를 통해 이어질 수 있는 경기결과들을 업데이트 해줍니다. 

    for k in range(n): # path via k+1
        for i in range(n):
            for j in range(n):
                # i+1 wins k+1 && k+1 wins j+1 -> i+1 wins j+1
                if dist_array[i][j] == 0 and dist_array[i][k] and dist_array[k][j]:
                    dist_array[i][j] = 1

실제로 업데이트 되는 과정입니다. 

 

initial 

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

 

step 1

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

 

step 2

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

 

step 3

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

 

step 4

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

 

step 5

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

 

이후에 1번선수의 순위가 판단이 가능한지는

1번 선수 row의 1의 갯수 + 1번 선수 column의 1의 갯수 = n-1 인가로 판단 할 수 있습니다.

 

실제 구현된 코드는 아래와 같습니다. 

# Floyd-Warshall Algorithm
def solution(n, results):

    dist_array = [[0]*n for _ in range(n)]
    
    for result_win, result_lose in results:
        dist_array[result_win-1][result_lose-1] = 1

    for k in range(n): # path via k+1
        for i in range(n):
            for j in range(n):
                # i+1 wins k+1 && k+1 wins j+1 -> i+1 wins j+1
                if dist_array[i][j] == 0 and dist_array[i][k] and dist_array[k][j]:
                    dist_array[i][j] = 1
    
    column_sum = [0]*n
    row_sum = [0]*n
    for row in range(n):
        for column in range(n):
            column_sum[column] += dist_array[row][column]
            row_sum[row] += dist_array[row][column]
    
    answer = 0
    for index in range(n):
        if column_sum[index] + row_sum[index] == n-1:
            answer+=1

    return answer