10159 저울 [파이썬]

문제)

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

10159번: 저울

 

처음부터 접근 방법이 잘못돼 한참을 헤매었다.

bfs로 풀려고 했는데 나중에 보니 간선의 가중치가 다르더라... 그걸 너무 늦게 깨달았다.

bfs, dfs는 간선의 가중치가 1로 다 같을 때 쓸 수 있는 것인데.... ㅠㅠ

 

소스코드)

n = int(input())
m = int(input())
dp = [[inf] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if i==j:
            dp[i][j] = 0

for i in range(m):
    a, b = map(int, input().split())
    dp[a][b] = 1

for k in range(1, n+1): # node k
    for a in range(1, n+1): # start a
        for b in range(1, n+1):
            dp[a][b] = min(dp[a][b], dp[a][k] + dp[k][b])

#print(*dp, sep="\n")
for a in range(1, n+1):
    count = 0
    for b in range(1, n+1):
        if dp[a][b] == inf and dp[b][a] == inf:
            count += 1
    print(count)

 

내가 처음 시도한 소스코드는 창피해서 못 올리겠다..