BOJ - 저울(10159)

골드3 : 최단 경로 문제이다.

풀이

이전에 풀었던 문제와 매우 비슷한데 음,.., 아 분명히 풀었다. 아마 프로그래머스 문제였던 것 같다. 연결되어 있는지 모두 파악하는 문제였다.

Code

import sys
from pprint import pprint
 
input = sys.stdin.readline
 
n = int(input())
m = int(input())
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
 
for _ in range(m):
    a, b = map(int, input().split())
    dp[a][b] = 1
 
 
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if dp[i][k] and dp[k][j]:
                dp[i][j] = 1
 
for i in range(1, n + 1):
    ans = 0
    for j in range(1, n + 1):
        if i == j:
            continue
        if dp[i][j] == 0 and dp[j][i] == 0:
            ans += 1
    print(ans)

Reference

• 백준(10159번) - 저울