[Dynamic Programming] 행렬 경로 문제

문제

* 아래 문제의 recursive property를 제시하라.

 

양 또는 음의 정수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다.

 

이동 방법 (제약조건)

- 오른쪽이나 아래쪽으로만 이동할 수 있다.

- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.

 

목표

행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최소화되도록 한다.

 

불법 이동 예

 

 

유효한 이동의 예

 

 

문제풀이 방법

 

1. 초기화

- dp[0][0] = matrix[0][0]: 시작점은 그대로 자신의 값으로 초기화

- 첫 행과 첫 열은 이전 값에 현재 칸의 값(matrix의 값)을 더하여 초기화 (for문)

 

2. 점화식 dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i][j-1])

- 현재 칸 (i, j)까지의 최소 경로 합은 현재 칸의 값(matrix[i][j])에 아래 두 경우 중 작은 값을 더한다

• 왼쪽 (i-1, j)에서 오는 경우의 값
• 위쪽 (i, j-1)에서 오는 경우

3. DP테이블 채우기

- 이중 반복문을 통해 DP 테이블을 채워나간다.

- 이 과정을 통해 좌상단에서 우하단까지의 모든 칸에 대한 최소 경로 합을 계산할 수 있다

 

4. 결과

DP 테이블의 우하단 칸 dp[n-1][n-1]에 저장된 값이 좌상단에서 우하단까지의 최소 경로 합이 된다.

 

 

코드
C++

def min_path_sum(matrix):
    n = len(matrix)
    # 최소 경로 합을 저장할 2차원 DP 테이블 생성
    dp = [[0] * n for _ in range(n)]
    
    # DP 테이블 초기화
    dp[0][0] = matrix[0][0]
    
    # 첫 번째 행 채우기
    for i in range(1, n):
        dp[0][i] = dp[0][i-1] + matrix[0][i]
    
    # 첫 번째 열 채우기
    for j in range(1, n):
        dp[j][0] = dp[j-1][0] + matrix[j][0]
    
    # 나머지 DP 테이블 채우기
    for i in range(1, n):
        for j in range(1, n):
            dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    # DP 테이블의 우하단 칸 값이 최소 경로 합
    return dp[n-1][n-1]

# 예제 사용
matrix = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print(min_path_sum(matrix))  # 출력: 7

 

Python

 

def min_path_sum(matrix):
    n = len(matrix)
    # 2차원 배열인 dp테이블 생성
    dp = [[0] * n for _ in range(n)]
    
   #DP테이블 초기화
    dp[0][0] = matrix[0][0]
    
   # 1행은 이전 값으로 채우기
    for i in range(1, n):
        dp[0][i] = dp[0][i-1] + matrix[0][i]
    
    # 1열은 이전 값으로 채우기
    for j in range(1, n):
        dp[j][0] = dp[j-1][0] + matrix[j][0]
    
    # 1행과 1열을 제외한 나머지 칸수 채우기
    for i in range(1, n):
        for j in range(1, n):
            dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    #오른쪽 가장 아래의 값 출력
    return dp[n-1][n-1]

#예시
matrix = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print(min_path_sum(matrix))  # Output: 7