[프로그래머스] 등굣길(42898)

1. 문제 풀이 아이디어

• 동적 프로그래밍(dp)을 사용해 문제를 해결할 수 있다.

• 문제에서 1000000007로 나눈 나머지를 반환하라고 명시되어 있으므로 이를 무시하면 효율성 테스트를 통과하지 못한다. 따라서 문제를 꼼꼼히 읽고 조건을 정확히 반영해야 한다.

2. 나의 정답 코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        boolean[][] map = new boolean[n + 1][m + 1];
        int[][] dist = new int[n + 1][m + 1];
        for (int[] puddle : puddles) {
            map[puddle[1]][puddle[0]] = true;
        }
        dist[0][1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (map[i][j]) continue;
                dist[i][j] = dist[i - 1][j] + dist[i][j - 1];
                dist[i][j] %= 1000000007;
            }
        }
        return dist[n][m];
    }
}

3. 정리

• dp 구현을 위해 2차원 배열의 크기를 기존보다 1씩 증가시켜 정의한다.

• 웅덩이 위치를 저장하기 위해 boolean 타입의 2차원 배열을 사용하며, 웅덩이가 있는 좌표는 true로 설정한다.

• 최단 경로의 경우의 수를 저장하기 위해 int 타입의 2차원 배열을 활용한다.

• for 문을 사용해 각각의 좌표에서 위쪽(i-1)과 왼쪽(j-1) 위치의 경우의 수를 더한 값을 dist[i][j]에 저장한다.

• 이후 1000000007로 나눈 나머지를 저장해 문제의 조건을 만족시킨다.

• 최종적으로 dist[n][m] 값을 반환해 문제를 해결한다.