[파이썬]최단경로 알고리즘

 

import random

mat = [[random.choice(range(50)) for _ in range(10)] for _ in range(10)]

m = len(mat)

len(mat)

for i in range(m):
    print(mat[i])

def matrixPath(i, j):
    if i == 0 and j == 0:
        return mat[i][j]
    if j == 0:
        return matrixPath(i-1, 0) + mat[i][0]
    if i == 0:
        return matrixPath(0, j-1) + mat[0][j]
    
    return min(matrixPath(i-1, j) + mat[i][j], matrixPath(i, j-1) + mat[i][j]) 

%timeit matrixPath(m-1, m-1)

memo = [[] for _ in range(m)]

memo

for i in range(m):
    for j in range(len(mat[i])):
        memo[i].append(-1)

memo

def matrixPath_memo(i, j):
    if memo[i][j] != -1:
        return memo[i][j]
    
    if i == 0 and j == 0:
        memo[i][j] = mat[i][j]
    elif j == 0:
        memo[i][0] = matrixPath_memo(i-1, 0) + mat[i][0]
    elif i == 0:
        memo[0][j] = matrixPath_memo(0, j-1) + mat[0][j]
    else:
        memo[i][j] = min(matrixPath_memo(i-1, j) + mat[i][j], 
                                   matrixPath_memo(i, j-1) + mat[i][j]) 
        
    return memo[i][j]

%timeit matrixPath_memo(m-1, m-1)

for i in range(m):
    print(memo[i])

memo[5][5]