[Programmers 49191] 순위

문제

LV3 [Programmers 49191 - 순위]

문제 풀이 방법

처음에는 크루스칼 알고리즘으로 최장 신장 트리를 구하여 각 트리의 레벨에서 하나만 있는 노드의 개수를 세는 방법을 생각하였지만 이는 너무 어려운 접근이였다. 이 문제는 다양한 풀이법이 존재하지만 나는 플로이드-워셜 알고리즘으로 풀이하였다.

n명의 선수가 존재할 때, 다른 n-1 선수들과의 승패를 결정할 수 있으면, 순위가 정해진다.

1. 각 선수들의 승패를 저장하는 2차원 배열을 생성하고 경기 결과를 이차원 배열에 표시한다. 이 때, 승리한 경우 1, 진 경우에는 -1로 표시한다.
2. 플로이드-워셜 알고리즘을 수행한다. 배열을 순회하며 만약 해당 배열의 승패를 알 수 있는 경우 정보를 표시한다. 예를 들어 arr[a][c] 와 arr[c][b]가 모두 1이라면 arr[a][b]도 1이다.
3. 각 행을 돌면서 승패 정보를 n-1개 알고 있다면 answer+1을 해준다.

풀이 코드

Python

def solution(n, results):
    answer = 0

    arr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for x,y in results:
        arr[x][y] = 1
        arr[y][x] = -1

    for k in range(1, n+1):
        for i in range(1,n+1):
            for j in range(1, n+1):
                if arr[i][j] == 0 and arr[i][k] == arr[k][j] == 1:
                    arr[i][j] = 1
                elif arr[i][j] == 0 and arr[i][k] == arr[k][j] == -1:
                    arr[i][j] = -1
    for row in arr[1:]:
        # print(row)
        if row[1:].count(0) == 1:
            answer+=1
    return answer

print(solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]), 2)