[백준] 10159 저울 (Python/파이썬) - 플로이드워셜

https://www.acmicpc.net/problem/10159

플로이드워셜 알고리즘을 이용하면 날먹할 수 있는 문제이다 

왜 플로이드 워셜이냐?! 라고 한다면.. 모든 1 ~ N번 노드가 자기자신을 기준으로 했을때 자신을 제외한 모든 노드까지 도달할 수 있는지를 확인하기 때문이다

입력에서 주어지는 순위는 한방향 그래프라고 이해할 수 있다 따라서 graph[a][b] =1 (a>b인 경우) 저장해서 경로가 있음을 표시했다. 

 

n = int(input()) # node
m = int(input())

graph = [[0] * (n+1) for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split()) # a > b  
    graph[a][b] = 1  # 순위를 알 수 있는 경우 
 #   graph[b][a] = 1 


for k in range(1, n+1):
    for x in range(1, n+1):
        for y in range(1, n+1):
            if graph[x][k] == 1 and graph[k][y] == 1:
                graph[x][y] = 1 # 순위 알 수 있음  

for i in range(1, n+1):
    count = 0
    for j in range(1, n+1):
        if graph[i][j] == 0 and graph[j][i] == 0:
            count += 1
    print(count-1)