BOJ - 10159

백준 문제 링크
저울

❓접근법

1. 플로이드 워셜 알고리즘을 활용했다.
2. 기본 플로이드 워셜 소스코드를 전개해
   최단 거리 테이블을 갱신해준다.
3. 2중 반복문으로
   graph[i][j]의 값과 graph[j][i]의 값이 둘다 INF이면
   cnt를 1 증가시키고 반복문 밖에서 cnt를 출력한다.

👌🏻코드

n = int(input())
m = int(input())

INF = int(1e9)

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0
            
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
                

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