[프로그래머스] 순위 (Python)

코딩테스트 연습 - 순위 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 순위

 

처음에는 딕셔너리와 세트로 풀이했는데 시간 초과가 났다. (시초 안 나는 풀이도 있다!!)

기왕 문제 종류가 그래프인만큼 다른 풀이 방법을 떠올려 보려고 했지만 쉽지 않았다...

그런데 질문을 보니 어떤 천사분께서 플로이드-와샬을 써보라고 하신 것을 보고... 바로 풀렸다!!

 

플로이드-와샬 알고리즘은 원래 모든 노드로부터 다른 노드까지의 최단 거리를 저장하는 알고리즘이다.

이때, 전체 알고리즘은 삼중 반복문으로 수행되는데 다음과 같다.

# n = 노드 개수

for k in range(n):			# 모든 노드를 중간점으로 삼으면서
	for i in range(n):		# 거리행렬을 순회
    	for j in range(n):	
            if arr[i][j] < arr[i][k] + arr[k][j]:	# 이때, 원래 저장돼 있던 i부터 j까지의 거리보다 
                arr[i][j] = arr[i][k] + arr[k][j]	# k를 거쳐가는 i-k-j 거리가 더 짧다면 갱신함

 

이 문제에서는, 거리가 아니라 승패 여부만 저장한다고 보면 된다.

1. 거리행렬 이기면 1, 지면 -1, 모르면 0로 초기화 해놓는다.

2. 반복문을 수행하면서, i-j에 대한 승패를 모르면(그 자리가 0이면) k를 중간기준으로 삼는다.

3. i가 k를 이기고 k가 j를 이겼다면, i는 j를 무조건 이긴다. 따라서 그 자리를 1로 갱신한다.

4. 지는 것도 똑같이 진행한다.

5. 알고리즘이 끝나면, 자기자신을 제외한 모든 노드에 대해 승패가 가려진 노드만 센다.

from collections import Counter


def solution(n, results):
    # p1이 p2에 이겼을 때는 1로,
    # p1이 p2에 졌을 때는 -1로 초기화
    board = [[0] * n for _ in range(n)]
    for p1, p2 in results:
        board[p1 - 1][p2 - 1] = 1
        board[p2 - 1][p1 - 1] = -1

    for k in range(n):                  # 1. 모든 노드를 중간점(경로)로 가정하며
        for i in range(n):              # 2. 점수판을 순회
            for j in range(n):          # 3. 만약 i가 k에 이겼고, k가 j에 이겼다면
                if board[i][j] == 0:    # i는 j에게도 이김 (지는 것도 동일)
                    if board[i][k] == 1 and board[k][j] == 1:
                        board[i][j] = 1
                    elif board[i][k] == -1 and board[k][j] == -1:
                        board[i][j] = -1

    # 각 노드 점수판에 0이 하나(다른 노드들에 대해 승패가 모두 결정됨)인 경우만 셈
    ans = 0
    for i in range(n):
        if Counter(board[i])[0] == 1:
            ans += 1

    return ans