10159. 저울 (Python)

10159번: 저울

 

풀이

 플로이드 워셜을 사용하여 구현할 수 있다.

 a > b, b > c일 경우 a > c라는 개념을 사용한다. 

 

코드

import sys
input = sys.stdin.readline
INF = float('inf')

if __name__ == '__main__':
    N = int(input())  # 물건의 개수
    M = int(input())  # 미리 측정된 물건 쌍의 개수
    
    # comparison[i][j] = 1 -------------->   i > j를 의미
    # comparison[i][j] = -1 ------------->   j > i를 의미 
    # comparison[i][j] = INF ------------>   비교불가를 의미 
    comparison = [[INF for _ in range(N)] for _ in range(N)] 

    for i in range(N):
        comparison[i][i] = 1

    for _ in range(M):
        a, b = map(int, input().split())
        comparison[a-1][b-1] = 1  # 앞의 물건이 뒤의 물건보다 더 무겁기 때문에 [a][b]를 1로 설정
        comparison[b-1][a-1] = -1

    # 플로이드 워셜 알고리즘 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                # i >k이고 k > j이면 i > j이다.
                # comparison[j][i]는 -1로 설정한다.
                if comparison[i][k] == 1 and comparison[k][j] == 1:
                    comparison[i][j] = 1
                    comparison[j][i] = -1 

    for i in range(N):
        print(comparison[i].count(INF))