🥚

Recent Notes

See 20 more →

BOJ - 경로찾기(11403)

2 min read

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

생각

  1. 모든 경로에 대한 최단 거리를 구해야 한다.
  2. 가중치는 양수이자 동일
  3. 정점 개수 100개

모든 경로에 대해 최단 거리를 구해야 한다는 점에서 플루이드를 사용할 것이고, 알고리즘에도 통과한 노드 개수이므로 진행한다. (제한시간 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

Graph