[프로그래머스] 순위 #파이썬 #그래프 #Floyd-Warshall #Level3

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

코딩테스트 연습 - 순위

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

풀이

일단 문제를 읽고 이 문제가 그래프인지, 이분 탐색인지, 아니면 dp인지 등등 어떤 유형인지 감이 잡혀야 합니다. 물론 연습문제인지라 구분은 그래프로 되어있으나, 직접 생각해보는 것이 중요합니다. 실제로 저는 문제를 처음 봤을 때 풀이법이 정렬, 내지는 해쉬를 이용하여야 할 것 같다는 느낌이 들었습니다. 문제 구분이 그래프인지라 무지성 BFS, DFS도 한 번씩 해보고 union-find로 부모를 찾아야 하나? 싶기도 했네요.

이 문제를 풀기 위해선, 먼저 '순위'가 무엇인지 명확히 정의하는 것이 필요합니다. n명이 존재할 때 i 번째 사람의 순위는, i 번째 사람이 다른 사람과 n-1 번 싸워 이기던가, 이미 순위가 결정된 사람과 싸워 나온 승패를 이용하여 알 수 있습니다. 바로 갈 수도 있고, 한 다리 (혹은 여러 다리) 건너건너 알 수도 있는 것이지요. 한 점에서 다른 점까지의 거리를 (한 다리 거쳐서) 찾을 수 있는 알고리즘은 무엇일까요? 저는 Floyd-Warshell 알고리즘이 떠올랐습니다. for loop 세 번만 써주면 되어서 구현도 쉽고요.

Floyd-Warshell 알고리즘은 그래프가 Adjacency Matrix 형식으로 표현되었을 때 사용할 수 있는 알고리즘입니다. 따라서 입력 값을 Adjacency Matrix 형태의 그래프로 변환하겠습니다. 구분을 위해 연결되지 않은 부분은 None, 이긴 쪽은 True, 진 쪽은 False로 구분했습니다.

matrix = [[None for _ in range(n)] for _ in range(n)]
for win, lose in results:
    matrix[win-1][lose-1] = True
    matrix[lose-1][win-1] = False

다음으로 Floyd-Warshell 알고리즘입니다. Floyd-Warshell 알고리즘의 기본적인 논리는 j 점에서 k점을 갈 때 i 점을 거쳐 j -> i -> k로는 갈 수 있는가? 입니다. 일반적인 경우, 이렇게 가는 것이 비용이 더 작은가? 에 대한 평가, if 문이 들어가지만, 우리는 연결만 되어 있으면 되겠죠.

for i in range(n):
    for j in range(n):
        for k in range(n):
            if matrix[j][i] == None:
                continue

            if matrix[j][i] == matrix[i][k]:
                matrix[j][k] = matrix[j][i]
                matrix[k][j] = not matrix[j][i]

j -> i 가 False이고 i -> k 가 False라면 이는 j가 i에게, i가 k에게 졌다는 것을 의미합니다. 그렇다면 matrix[j][k]는 False가 되겠네요. matrix[k][j]는 True가 되고요. 해당 if 문은 반대의 경우에도 마찬가지로 적용됩니다. 이제 연결되지 않은?? 연결 상태가 이상한? 노드를 찾아야 합니다. 모든 노드와 비교되거나, 간접 비교 되지 않은 노드를 찾아야겠죠. 이러한 노드는 None을 하나 넘게 가지고 있습니다. (matrix[i][i] = 자기 자신 = None이기 때문에 무조건 하나는 가지고 있습니다.) None이 하나인 노드만 세어 정답을 ++ 해줍니다.

answer = 0
for i in range(n):
    if None in matrix[i][:i] + matrix[i][i+1:]:
        continue
    answer += 1

전체 코드입니다.

def solution(n, results):
    matrix = [[None for _ in range(n)] for _ in range(n)]
    for win, lose in results:
        matrix[win-1][lose-1] = True
        matrix[lose-1][win-1] = False
        
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if matrix[j][i] == None:
                    continue
                    
                if matrix[j][i] == matrix[i][k]:
                    matrix[j][k] = matrix[j][i]
                    matrix[k][j] = not matrix[j][i]
                    
    answer = 0
    for i in range(n):
        if None in matrix[i][:i] + matrix[i][i+1:]:
            continue
        answer += 1
    return answer