[김태원 알고리즘] 플로이드 워샬 알고리즘

사용 언어: Python3

문제

풀이

내 풀이

N, M = map(int, input().split())
G = [[1000] * N for _ in range(N)] # ✅ 초기화는 1000으로 ('M'으로 하면 뒤에 계산 복잡해짐)

# 자신에서 자신은 0으로
for i in range(N):
    G[i][i] = 0

for _ in range(M):
    src, dest, w = map(int, input().split())
    G[src-1][dest-1] = w

# ✅ 플로이드-워샬
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][k] + G[k][j], G[i][j])

for i in range(N):
    for j in range(N):
        print([G[i][j], 'M'][G[i][j] == 1000], end = ' ') # ✅ 값이 1000 일 경우 'M'으로 출력
    print()

• 정답!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기