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

풀이

def solution(n, results):
    board = [[None for _ in range(n)] for _ in range(n)]
    # 이겼으면 True, 졌으면 False
    # board = [[None, True, None, None, None], [False, None, False, False, True], [None, True, None, False, None], [None, True, True, None, None], [None, False, None, None, None]]
    for win, lose in results:
        board[win-1][lose-1] = True
        board[lose-1][win-1] = False
    
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if board[j][i] == None:
                    continue
                # j가 i에게 졌고, i가 k에게 졌다면
                # j가 k에게 졌다는 것을 의미하고
                # k는 j에게 이겼다는 것을 의미
                if board[j][i] == board[i][k]:
                    board[j][k] = board[j][i]
                    board[k][j] = not board[j][i]
    answer = 0
    # 자기 자신 None만 가지고 있는 노드만 찾는다.
    # board = [[None, True, None, None, True], [False, None, False, False, True], [None, True, None, False, True], [None, True, True, None, True], [False, False, False, False, None]]
    for i in range(n):
        if None in board[i][:i] + board[i][i+1:]:
            continue
        answer += 1
    return answer

• 문제를 읽고 어떤 유형인지 감이 잡혀야한다..
• 먼저 '순위'가 무엇인지 명확히 정의하라
  • n명이 존재할 때, i번째 사람의 순위는 i번재 사람이 다른 사람과 n-1번 싸워 이기던가 이미 순위가 결정된 사람과 싸워 나온 승패를 이용하여 알 수 있다.
  • 즉, 바로 갈 수도 있고, 한 다리 건너건너 알 수 있는 것
  • 플로이드 와샬 알고리즘 이용
•