[프로그래머스] 순위 - Python

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

프로그래머스

 

풀이

from collections import Counter
def solution(n, results):
    answer = 0
    board = [[0] * n for _ in range(n)]

    # 이겼으면 1 졌으면 -1로 표시해주기
    for a, b in results:
        board[a - 1][b - 1] = 1
        board[b - 1][a - 1] = -1

    # i가 k를 이기고 k가 j를 이겼으면 i는 j를 이긴다
    # 졌을때도 마찬가지
    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이 하나인 경우(다른 노드들에 대해 승패가 모두 결정되어 순위를 매길 수 있을 때)만 센다
    for row in range(n):
        if Counter(board[row])[0] == 1:
            answer += 1

    return answer

 

문제 접근 방법을 모르겠어서 찾아봤더니 플로이드 워셜 알고리즘을 이용해 풀 수 있었다!
아직 뭔가 제대로 이해를 못한 것 같은데 나중에 꼭 다시 한 번 더 풀어봐야지!!