문제 설명

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

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

제한사항

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

풀이

풀다가 도저히 생각이 안 나서 다른사람의 풀이를 참고했다.
이 문제의 핵심은
플로이드-워셜 알고리즘이다.

플로이드-워셜 알고리즘이란?

모든 경로에서의 최단거리를 구하는 알고리즘

2차원 테이블에서
3중 for문을 돌며 k 를 거쳤을때와 안 거쳤을때의 가중치를 비교에 더 짧은 거리를 계속 갱신하는 알고리즘이다

# n은 노드수
for k in range(n):
	for i in range(n):
    	for i in range(n):
        	if arr[i][j] > arr[i][k] + arr[k][j]: # 원래 i->j 가 i->j->k 보다 길면
            	arr[i][j] = arr[i][k] + arr[k][j] # 갱신

이번 문제에서는
가중치가 없기 때문에
테이블을 이기면 1 지면 -1 모르면 0으로 초기화 해준다.

그리고 3중 for문으로 모든 노드를 순회하며

• i가 j랑 승부를 했는데 결과를 모를때 (0일때)만
• i가 k를 이기고 k가 j를 이기면 i가 j를 이긴것(1로 표시)으로 하고
• i가 k한테 지고 k가 j한테 졌으면 i가 j한테 진것(-1로 표시)으로 갱신해준다

마지막으로 자신을 제외한 모든 노드의 값이 1이나 -1로 정해지면
그것은 순위가 확정된 것이므로
0이 하나인 행의 개수를 세어주면 된다.

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):                  
        for i in range(n):              
            for j in range(n):          
                if board[i][j] == 0:   
                    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

플로이드-워셜이라는 알고리즘을 새로 알아간다!
다음에 나오면 기억해보자