프로그래머스 programers 등굣길 (42898)문제의 풀이와 해설을 합니다.

[프로그래머스] 코딩테스트 연습 > 동적계획법(Dynamic Programming) > 등굣길 (9305)

문제바로가기

이 문제의 핵심은 도달 가능한 지점의 개수 = 왼쪽개수 + 위쪽개수 가 핵심

 1(1,1) 1(1,2)
 1(2,1) 2(2,2)

그리드에서 (2,2) 위치 도달 개수는

• 왼쪽(2,1) 도달개수 1
• 위쪽(1,2) 도달개수 1
• 도착지점의 도달 개수는 결국 왼쪽에서 들어오는 길, 위쪽에서 들어 오는길 2가지 이므로
  결국 왼쪽+위쪽 의 개수가 된다.
• 웅덩이는 지나갈 수 없으므로 0이 되는 것

점화식으로 표현하면

point(n. m) = point(n, m -1) + point(n-1, m)

해결책

1. 그리드 배열의 인덱스는 0 부터 이나, 문제에서는 1 부터 이므로 배열[n+1][m+1] 선언한다.
2. 웅덩이는 선언된 그리드 배열에 -1 값으로 표시한다(처리 시 0은 아직 개수가 계산되지 않은 지점, -1은 웅덩이를 구별하기 위함)
3. 출발 지점 그리드[1][1] = 1로 설정한다.
4. 재귀를 사용하여 점화식을 그대로 표현 하여 구현한다.
5. 재귀에서 이미 point(1,1) 보다 이전 위치의 값은 은 0을 리턴, 처리된 값이 있다면 그값을 리턴, 웅덩이라면 0을 리턴 하도록 처리

주의

웅덩이 배열 값 [1,2] => [row, col] 이 아니라 반대 입니다. 이것 때문에 로직은 맞으나 테스트를 통과 못하여 한참을 찾았네요..ㅠ 즉 그리드에 웅덩이 값을 선언 할때 grid[2][1] = -1 이렇게 들어 가야합니다.

소스코드

class Solution {
    private static int[][] matrix;
    
    public static int solution(int m, int n, int[][] puddles) {
        matrix = new int[n+1][m+1];
        Arrays.stream(puddles).forEach(v -> matrix[v[1]][v[0]] = -1);
        matrix[1][1] = 1;
        return recursive(n,m);
    }

    private static int recursive(int row, int col) {
        if (row < 1 || col < 1 || matrix[row][col] < 0) return 0;
        if (matrix[row][col] > 0) return matrix[row][col];
        return matrix[row][col] = (recursive(row, col - 1) + recursive(row - 1, col)) % 1000000007;
    }
}