[백준] 10159번 - 저울 (파이썬)

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

# 저울
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())

arr = [[False]*(N+1) for _ in range(N+1)]
for a in range(1, N+1):
    for b in range(1, N+1):
        if a == b:
            arr[a][b] = False

for _ in range(M):
    a, b = map(int, input().split())
    arr[a][b] = True

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if arr[i][k] and arr[k][j]:
                arr[i][j] = True

for i in range(1, N+1):
    count = -1
    for j in range(1, N+1):
        if not arr[i][j] and not arr[j][i]:
            count += 1
    print(count)

 

플로이드와샬

1. 인접행렬을 선언하고 자기자신으로 가는 경우는 False로 초기화

2. 입력을 받으면서 True로 초기화

3. 플로이드 와샬

    - k를 거쳐서 가는 경로가 있으면 True

4. 모든 노드마다 i에서 j로 가는 경로도 없고 오는 경로도 없으면(연결X) count++

    - 각각 출력