이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 25 번째 글 입니다.
목차
실버1 : 최단거리 문제이다.
생각
- 모든 경로에 대한 최단 거리를 구해야 한다.
- 가중치는 양수이자 동일
- 정점 개수 100개
모든 경로에 대해 최단 거리를 구해야 한다는 점에서 플루이드를 사용할 것이고, $O(V^3)$ 알고리즘에도 통과한 노드 개수이므로 진행한다. (제한시간 1초)
Code
import sys
def read_input():
n = int(sys.stdin.readline().rstrip())
w = [
[int(x) if int(x) != 0 else 100000 for x in sys.stdin.readline().split()]
for y in range(n)
]
d = w
p = [[int(0) for x in range(n)] for y in range(n)]
return n, w, d, p
def allShortestPath(n, w, d, p):
for k in range(n):
for i in range(n):
for j in range(n):
if d[i][j] > d[i][k - 1] + d[k - 1][j]:
p[i][j] = k
d[i][j] = d[i][k - 1] + d[k - 1][j]
for i in range(n):
for j in range(n):
if d[i][j] == 100000:
d[i][j] = 0
else:
d[i][j] = 1
return d, p
def path(start, end, p):
return
def printOutput(mat):
n = len(mat)
m = len(mat[0])
for i in range(n):
for j in range(m):
print(mat[i][j], end=" ")
print()
n, w, d, p = read_input()
d, p = allShortestPath(n, w, d, p)
printOutput(d)