[Level 3] 순위

programmers.co.kr/learn/courses/30/lessons/49191#

코딩테스트 연습 - 순위

---

접근

이 문제를 풀면서 플로이드-와샬 알고리즘을 알게되었다.

플로이드-와샬은 모든 정점에서 모든 정점으로 이동할 때의 최소비용을 구할 때 사용할 수 있다.

예를 들어, i -> j로 이동할 때의 최소비용을 구하기위해 중간노드를 거쳐서 가는 비용으로 비교를 한다.

i -> k, k->j 로 이동할 때의 비용을 통해 최솟값 비교를 진행한다.

 

해당 개념을 이 문제에 어떻게 적용시킬 수 있을까?

5명의 사람들이 있고 2차원 리스트에 승부결과를 넣는다면 빈 공간은 아직 승부결과를 모른다는 것이다.

이때 중간 노드를 거쳐서 해당 공간(해당 매치)의 결과를 알 수 있는지 찾아본다.

 

5명이기 때문에 중간 사람을 1~5까지 순서대로 정하고 각 사람을 중간사람으로 기준으로 모든 승부에 대한 결과를 탐색한다. 모든 승부를 결정짓고 각 사람들이 결정된 매치가 4라면(n-1)이라면 순위를 매길 수 있다는 것이다.

 

구현

2차원 리스트에 매치의 결과를 적는다 이겼다면 1, 졌다면 -1로 표시를 한다.

    answer = 0
    score_board = [[0 for _ in range(n)] for _ in range(n)]
    for a, b in results:
        score_board[a-1][b-1] = 1
        score_board[b-1][a-1] = -1

 

k를 기준으로 i->j로 갈 수 있는지 찾아본다.

i->k, k->j가 1(-1)이면 i->j도 1(-1)로 표시를 한다.

여기서 왜 k를 가장 상단의 for문으로 정해야하는지 의문이었다.

모든 사람을 중간사람으로 기준하여 i-j의 결과를 구하는 것이다. 만약 i-j-k 순으로 for문을 구성한다면 1-2의 결과가 다른 경기에 영향을 받아 승부를 알 수 있을지도 모르는데 이러한 경우를 건너띄게된다. (이렇게 표현하는 것이 맞는지 모르겠다.) 즉 k가 가장 상단에 있어야 모든 사람을 기준으로 모든 경기의 결과를 탐색할 수 있다.

for k in range(n):
        for i in range(n):
            for j in range(n):
                if score_board[i][j] == 0:
                    if score_board[i][k] == 1 and score_board[k][j] == 1:
                        score_board[i][j] = 1
                    if score_board[i][k] == -1 and score_board[k][j] == -1:
                        score_board[i][j] = -1

 

위의 과정을 거친 후에 해당 줄에서 0의 개수가 1이라면 최종해를 증가시킨다.

for x in range(n):
        if Counter(score_board[x])[0] == 1:
            answer += 1

 

---

전체 코드

from collections import Counter
def solution(n, results):
    answer = 0
    score_board = [[0 for _ in range(n)] for _ in range(n)]
    for a, b in results:
        score_board[a-1][b-1] = 1
        score_board[b-1][a-1] = -1
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if score_board[i][j] == 0:
                    if score_board[i][k] == 1 and score_board[k][j] == 1:
                        score_board[i][j] = 1
                    if score_board[i][k] == -1 and score_board[k][j] == -1:
                        score_board[i][j] = -1
                        
    
    for x in range(n):
        if Counter(score_board[x])[0] == 1:
            answer += 1
    
    return answer