BOJ - 경로찾기(11403)

실버1 : 최단거리 문제이다.

생각

1. 모든 경로에 대한 최단 거리를 구해야 한다.
2. 가중치는 양수이자 동일
3. 정점 개수 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)
 
 

Reference

• 백준(11403번) - 포도주 시식