dynamic programming 행렬 최소 경로 구하기

soicem 2017. 6. 28. 23:55

test.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# dynamic programming 행렬 경로 문제
 
# target = [[10,30,25,8],
#           [19,50,11,3],
#           [32,51,3,5],
#           [6, 100,5,1]]
# cache = [[-1,-1, -1, -1],
#          [-1, -1, -1, -1],
#          [-1, -1, -1, -1],
#          [-1, -1, -1, -1]]
#
# direction = [[-1,-1, -1, -1],
#          [-1, -1, -1, -1],
#          [-1, -1, -1, -1],
#          [-1, -1, -1, -1]]
import random
 
target = []
cache = []
direction = []
 
size = 4 # 요 크기만 바꾸면 행렬 크기 변함
 
for i in range(0, size):
    target.append([])
    cache.append([])
    direction.append([])
    for j in range(0, size):
        target[i].append(random.randint(1, 100))
        cache[i].append(-1)
        direction[i].append(-1)
 
 
def matrixPath(i, j):
    if cache[i][j] is not -1:
        return cache[i][j]
    if i == 0 and j == 0:
        cache[i][j] = target[i][j]
        direction[i][j] = '-'
    elif i == 0:
        cache[i][j] = matrixPath(i, j-1) + target[i][j]
        direction[i][j] = 1 # 왼쪽
    elif j == 0:
        cache[i][j] = matrixPath(i-1, j) + target[i][j]
        direction[i][j] = 2 # 윗쪽
    else:
        minVal = min(matrixPath(i-1, j), matrixPath(i, j-1))
        cache[i][j] = minVal + target[i][j]
        if minVal == cache[i][j-1]:
            direction[i][j] = 1
        elif minVal == cache[i-1][j]:
            direction[i][j] = 2
 
    return cache[i][j]
 
def printMatrixMinPath(i, j):
    if i == 0 and j == 0:
        print("let's play ! ")
    elif direction[i][j] == 1:
        printMatrixMinPath(i, j-1)
    elif direction[i][j] == 2:
        printMatrixMinPath(i-1, j)
    print(i, ',', j)
 
i = len(target[0]) -1
j = len(target) -1
 
print("행렬 최소 경로 값은 ", matrixPath(i, j))
for el in cache:
    print(el)
printMatrixMinPath(i, j)
 
 
Colored by Color Scripter
cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
C:\Users\soicem\AppData\Local\Programs\Python\Python36-32\python.exe C:/Users/soicem/PycharmProjects/test/test.py
행렬 최소 경로 값은  298
[100, 169, 253, 342]
[159, 172, 214, 251]
[254, 242, 257, 348]
[269, 248, 290, 298]
let's play ! 
0 , 0
1 , 0
1 , 1
2 , 1
3 , 1
3 , 2
3 , 3
Colored by Color Scripter
cs

오른쪽, 아래로만 이동가능한 행렬의 최소 경로를 찾는 문제를 파이썬으로 구현해봤습니다.

ref : 영리한 프로그래밍을 위한 알고리즘 강좌 in inflearn