[백준] 11403 파이썬

문제

---

• 백준 11403 (실버1)

백준 11403

처음 봤을 때는 어떻게 푸는지 감이 안와서 고민해봤다.
정점의 개수가 100개 이하라는 것에서 삼중 for문까지도 가능하겠다는 생각이 들었다.
플로이드-워셜 알고리즘을 검색하여서 찾아봤다.

플로이드-워셜 알고리즘

---

• 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘
• 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징
• 점화식은 아래와 같다.

• 파이썬으로 나타낸 코드는 아래와 같다.

for k in range(1, n+1) :
    for a in range(1, n+1) :
        for b in range(1, n+1) :
            D[a][b] = min(D[a][b], D[a][k] + D[k][b])

내 코드

---

플로이드-워셜 알고리즘을 찾아보고 이를 활용하여서 코드를 작성하였다.
생각보다 굉장히 코드가 간단하게 나와서 알고리즘을 찾아보기 전에 미리 구현해볼걸 후회했다.

import sys
input = sys.stdin.readline

n = int(input())
g = []
for _ in range(n):
    g.append(list(map(int,input().split())))

for k in range(n):
    for a in range(n):
        for b in range(n):
            if g[a][k] == 1 and g[k][b] == 1:
                g[a][b] = 1

for arr in g:
    print(*arr)

알고리즘을 미리 알고 문제를 푸는 것보단 문제를 보면서 어떤 알고리즘을 사용할지 고민하는 습관을 길러야겠다.