[백준] 10159번 저울

💡문제접근

• 플로이드-워셜 알고리즘
• i에서 j로의 관계가 False, j에서 i로의 관계가 False인 경우 두 물건을 비교할 수 없다.

💡코드(메모리 : 31256KB, 시간 : 224ms)

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
graph = [[False] * (N+1) for _ in range(N+1)]
for _ in range(M):
    # a → b : a가 b보다 무겁다.
    a, b = map(int, input().strip().split())
    graph[a][b] = True

for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            if graph[a][b] == True or (graph[a][k] == True and graph[k][b] == True):
                graph[a][b] = True

for a in range(1, N+1):
    cnt = 0
    for b in range(1, N+1):
        if a == b:
            continue
        if not graph[a][b] and not graph[b][a]:
            cnt += 1
    print(cnt)

💡소요시간 : 24m