[알고리즘] m*n 격자 (1, 1)에서 오른쪽, 위쪽으로만 이동하여 (m, n)로 가는 최단 경로

문제 기술

다음과 같은 m개의 행과 n개의 열의 셀(cell)들로 이루어진 m*n 격자가 있다.여기서 가장 아래 행은 행 1이고 가장 위의 행은 행 m이며, 가장 왼쪽 열은 열 1이고 가장 오른쪽 열은 열 n이다. 셀 (i, j)는 i번째 행과 j번째 열의 셀을 나타낸다. 각 셀 (i, j)에는 비용 C(i, j)이 주어진다.

 

2	8	9	5	8
4	9	6	5	3
6	7	5	2	1
3	2	5	4	8

(1, 1)

 

셀 (1, 1)에서 오른쪽 방향 혹은 위쪽 방향으로만 가면서 셀 (m, n)까지 가는 경로의 최소비용을 구하는 프로그램을 동적계획법을 이용하여 작성하시오. 경로의 비용이란 지나가는 셀의 비용의 총합이다.

제약조건: 부분문제의 해의 값를 저장하는 테이블로 1차원 배열(리스트)를 사용해야 하고, 이 배열의 크기는 O(max(m,n))이어야 함.

입력

4 5 // m과 n

2 8 9 5 8

4 9 6 5 3

6 7 5 2 1

3 2 5 4 8

출력

28

15	23	30	26	28
13	21	21	21	20
9	12	15	16	17
3	5	10	14	22

(0, 0)

나의 코드

m, n = map(int, input().split())
C = [0] * m
A = [0] * n
A_copy = [0] * n
for i in range(m-1, -1, -1):
    C[i] = list(map(int, input().split()))

# base case
for a in range(n):
    if a == 0:
        A[a] = C[0][a]
    else:
        A[a] = A[a-1] + C[0][a]
    A_copy = A.copy()

for i in range(1, m):
    for j in range(n):
        if n == 1:
            A[j] += C[i][j]
        else:
            if j == 0:
                A[j] = A[j] + C[i][j]
            else:
                A[j] = C[i][j] + min(A[j-1], A_copy[j])
        A_copy = A.copy()
print(A[-1])

제약 조건이 있기 때문에, 부분해를 구하는 값 A는 일차원 배열이어야 하고, 그 크기는 m = 5, n = 4 기준 5가 되어야 한다.

우선 base case로 A의 첫 번째 줄을 구했다. 그 다음 이 값을 copy() 메소드를 이용해서 A_copy라는 배열에 따로 저장했고, 메인 for문을 돌면서 A의 이전 항(j-1)과 A_copy의 j번째 항(j)을 비교한 뒤 더 큰 것을 해당 셀의 비용에 더해줬다.