[프로그래머스/Lv.3] - 순위(Ref)

순위(문제 링크)

아이디어

처음에는 그래프 문제를 보고, 승/패를 하나의 차수로 생각해서 그래프 이론에서 적용할 수 있는 위상정렬 알고리즘으로 풀 수 있겠다고 정말 단순하게 생각했다.
그러나, 그림을 직접 그려보니 결과값이 어떠한 기준이 있지 않았다.
(위상 정렬 결과 : [1, 4, 3, 2, 5])
위상정렬은 노드들을 순서대로 정렬하는 것이 핵심인데, 이 문제에서는 어떠한 순서도 필요가 없고 정렬을 할 필요도 없기 때문이다.

✅ +) 위상정렬 알고리즘은 모든 순위가 정확히 나올 때 사용하는 알고리즘이다.

그저, 순위를 매길 수 있는 노드의 개수만 찾으면 된다.

다시 돌아와서, 순위에 집중해보았다.
순위란 어떻게 결정할 수 있는가?

1. 특정 노드 a의 순위를 결정할 수 있다면, 나머지 노드들과의 경기를 수행해야 한다.
2. 순위란 상대적인 것이다.

다시 말해,

• 'n개의 노드가 있다면, n - 1번의 경기를 수행해야 순위를 정할 수 있다'
• a가 b를 이기고, b가 c를 이기면 자동으로 a는 c를 이긴다.

즉, 플로이드-와샬 알고리즘을 적용하면 된다.

코드

def solution(n, results):
    rank = [[0] * n for _ in range(n)]
    
    # 1: 왼쪽이 오른쪽을 이겼다.
    # -1: 왼쪽이 오른쪽한테 졌다.
    # results는 1-index
    for a, b in results:
        rank[a - 1][b - 1] = 1 
        rank[b - 1][a - 1] = -1
        
    
    for k in range(n): # 경유점
        for i in range(n): # 시작점
            for j in range(n): # 끝점
                if i == j:
                    continue
                
                # i가 k를 이기고, k가 j를 이겼다 : i가 j를 이겼다.
                if rank[i][k] == rank[k][j] == 1:
                    rank[i][j] = 1 # 이겼음을 표시
                    rank[j][i] = rank[j][k] = rank[k][i] = -1 # 졌음을 표시. (not 이겼음 = 졌음)
    
    can_be_ranked = 0
    
    # 정확한 순위를 매길 수 있는지 확인하기
    # -1, 1은 경기를 했다는 의미 
    # 순위가 매겨지려면 n - 1번의 경기를 수행했어야 함.
    # 즉, 0이 1개라면 n - 1번의 경기를 했다는 의미이므로, 정확한 순위를 매길 수 있다.
    for r in rank:
        if r.count(0) == 1:
            can_be_ranked += 1
            
    return can_be_ranked

풀이

승/패를 다음과 같이 숫자로 정의했다.

• 승: 1
• 패: -1

새로운 리스트(graph)를 하나 만들어서, 경기 정보를 승/패로 다시 저장했다.
그리고, 플로이드-와샬 알고리즘으로 상대적인 순위를 계산하여 저장한다.

마지막으로는, 특정 노드가 경기를 n - 1번 수행했는지
즉, 정확한 순위를 매길 수 있는 노드인지 확인한다.