[프로그래머스] 순위 (플로이드-워셜, 그래프)

사용 언어: Python3

문제

순위

풀이

참고

from collections import Counter

def solution(n, results):
    board = [[0] * n for _ in range(n)]
    for win, lose in results:
        board[win-1][lose-1] = 1 # ✅ win이 lose를 이김(1)
        board[lose-1][win-1] = -1 # ✅ lose는 win에게 짐(-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 row in board:
        if Counter(row)[0] == 1: # ✅ row에서 0의 개수 카운트
            ans += 1
    return ans

• 정답!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기