[알고리즘] 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	4	6	5	3
5	7	5	1	1
3	2	5	4	8

가장 아래 행의 셀로부터 오른쪽 위쪽 대각선 방향 혹은 위쪽 방향 혹은 왼쪽 위쪽 대각선 방향으로만 가면서 가장 위의 행의 셀까지 가는 경로의 최소비용을 구하는 프로그램을 동적계획법을 이용하여 작성하시오. 경로의 비용이란 지나가는 셀의 비용의 총합이다.

제약조건: 부분문제의 해의 값를 저장하는 테이블로 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

출력

13

13	19	19	13	16
11	11	11	11	8
7	9	7	5	5
3	2	5	4	8

(0, 0)

나의 코드

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

# base case
for a in range(n):
    A[a] = C[0][a]

A_copy = [0] * n

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

이번 문제 또한 부분해를 저장하는 리스트 A가 1차원 배열이어야 하고, 그 크기는 m = 5, n = 4 기준 5가 되어야 한다.

우선 base case로 첫 번째 A의 행을 구했다. 첫 줄은 그대로 C의 첫 줄인 3 2 5 4 8이 들어간다.

두 번째 줄부터 메인 for문에 들어가는데, 이 때도 i가 1인가 아닌가에 따라 다르다. (1이면 두 번째 줄, 그 이후로는 세 번째 줄 이후)

 

1) i가 1인 경우

- A의 값은 C의 값만으로 구할 수 있다. j가 0이라면 왼쪽 아래의 값이 없고, j가 n-1이라면 오른쪽 아래의 값이 없으므로

0일 때는 바로 아래와 오른쪽 아래 값 중 작은 값을 더해줬고, n-1일 때는 바로 아래와 왼쪽 아래 값 중 작은 값을 더해줬다.

그리고 for문이 끝날 때마다 A_copy에 A를 복사한 값을 부여해줬다.

copy() 메소드를 사용한 이유: A_copy = A로 할 경우, 두 개가 같이 움직인다. A의 값을 변경해줬을 때 A_copy의 값도 변경이 된다. 따라서 copy() 메소드를 사용하여 A의 값이 변하더라도 A_copy의 값은 변하지 않게 했다.

 

2) i가 2 이상인 경우

- A는 1차원 배열이어야 하기 때문에 매번 업데이트되는 A의 값 내부에서 비교할 게 아니라, 이전 줄인 A_copy의 값에서 1)과 똑같은 방식으로 비교를 해야 한다. 1)과 로직이 똑같으므로 따로 적지 않겠다.

이번에도 마찬가지로 for문이 끝날 때마다 A_copy에 A를 복사한 값을 부여해줬다. 그래야 다음 줄에서 이전 A의 값을 참고할 수 있기 때문이다.