[BaekJoon] 백준 10159번 저울

[BaekJoon] 백준 10159번 저울

 

🎈문제

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

💬설명

• 플로이드-와샬로 모든 점에서 다른 모든 점으로 갈 수 있는지를 모두 구하고, a -> b, b -> a인 경로가 있다면 무게 비교가 가능한 개수에 추가해서 출력하면 된다.

👩‍💻코드

# BaekJoon10159.py

N = int(input())
M = int(input())
relation = [[False for _ in range(N)] for _ in range(N)]

# 연결 배열 생성
for _ in range(M):
    a, b = map(int, input().split())
    relation[a - 1][b - 1] = 1
    
# 플로이드-와샬로 이동 가능한 보든 경로 구하기
for k in range(N):
    for i in range(N):
        for j in range(N):
            if relation[i][k] and relation[k][j]:
                relation[i][j] = True
                
# 출력
for i in range(N):
    cnt = 0
    for j in range(N):
        if not relation[i][j] and not relation[j][i]:
            cnt += 1
    print(cnt - 1)