[알고리즘][동적계획법] 격자상의 경로

격자상의 경로 문제

n x n 격자가 있을 때 왼쪽 위 지점에서 오른쪽 아래 지점으로 가는 경로를 구하는 문제입니다. 이때 조건은 움직이는 방향은 오른쪽과 아래만 가능합니다. 결과는 경로가 지나가는 지점의 값을 모두 더한 값이 가장 커야 합니다.

 

격자상의 경로 예시

예를 들어 5 x 5 격자에서 최적 경로는 다음과 같습니다. 결과는 67입니다. 이 값이 왼쪽 위에서 오른쪽 아래로 가는 경로 중 가능한 최대의 값입니다.

격자상의 경로 접근

• 격자의 행과 열의 번호가 0~n-1이고 value[y][x]가 (y,x) 지점의 값이라고 가정
• 왼쪽 위 지점에서 (y,x) 지점까지의 경로의 최대값을 sum(y,x)로 나타내기로 함

 

점화식

sum(y,x) = max(sum(y, x-1), sum(y-1, x)) + value[y - 1][x - 1]

• sum(y, x-1) : sum(y,x)의 왼쪽 칸으로써 (y, x-1)칸까지의 경로의 최대값을 의미함
• sum(y-1, x) : sum(y,x)의 위쪽 칸으로써 (y-1, x)칸까지의 경로의 최대값을 의미함
• 왼쪽칸과 위쪽칸의 최대값들중 더 큰값을 선택하고 (y,x)의 값을 더하여 저장합니다.
• value[y - 1][x - 1] : value[y][x]가 아닌 이유는 value의 배열이 0부터 시작하기 때문입니다.

 

소스코드

public class MatrixPath {
    public int solution(int[][] value){
        int n = value.length;
        int[][] sum = new int[n + 1][n + 1];
        for(int y = 1; y <= n; y++){
            for(int x = 1; x <= n; x++){
                sum[y][x] = Math.max(sum[y][x - 1], sum[y - 1][x]) + value[y - 1][x - 1];
            }
        }

        return sum[n][n];
    }
}

public class MatrixPathTest {
    @Test
    public void testSolution(){
        //given
        int[][] value = {{3, 7, 9, 2, 7},
                        {9, 8, 3, 5, 5},
                        {1, 7, 9, 8, 5},
                        {3, 8, 6, 4, 10},
                        {6, 3, 9, 7, 8}};
        //when
        int actual = new MatrixPath().solution(value);
        //then
        Assertions.assertThat(actual).isEqualTo(67);
    }
}

 

References

source code : https://github.com/yonghwankim-dev/algorithm_training/tree/main/src/main/java/kr/yh/chap06_dp/matrixPath
알고리즘 트레이닝