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

문제 링크

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

풀이 과정

저는 일반적으로 아래와 같은 배열을 3 X 4 행렬로 받아들이기 때문에, 풀이에 앞서 문제에서 주어지는 배열의 크기 및 puddles 의 좌표는 반대 방향 이라는 걸 주의해야 했습니다.

m과 n이 주어지면 배열은 n x m 크기로 생성해야 되고, 행과 열의 크기가 반대로 주어지는 것을 토대로 puddles 의 좌표도 반대로 생각해야 합니다.

위 지도에서 빨간 원으로 가기 위한 최단 경로 는 세 개의 화살표로 표시된 경로와 같습니다. 사실상 최단 경로라는 말의 뜻도 필요가 없는데, 집에서 학교로의 진행은 오른쪽과 아래 두 방향으로밖에 이동하지 못하기 때문입니다. 따라서, 방향만 잘 지켜준다면 좌표로 향하는 모든 경로가 최단 경로가 됩니다.

빨간 원 기준으로 위 칸에 해당하는 노란 원을 지나는 경로의 수와, 왼쪽 파란색 원을 지나는 경로의 수를 더해주면 빨간 원 좌표에 도달하는 경로 갯수의 총 합을 결정지을 수 있게 됩니다.

코드

public class Main {
    public static int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n + 1][m + 1];
        final int MOD = 1000000007;

        for (int i = 0; i < puddles.length; i++) {
            map[puddles[i][1]][puddles[i][0]] = -1;
        }

        map[1][1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (map[i][j] == -1) {
                    map[i][j] = 0;
                    continue;
                }

                if (i - 1 >= 1) {
                    map[i][j] = (map[i][j] + map[i - 1][j]) % MOD;
                }
                if (j - 1 >= 1) {
                    map[i][j] = (map[i][j] + map[i][j - 1]) % MOD;
                }
            }
        }

        return map[n][m];
    }

    public static void main(String[] args) {
//        int m = 4;
//        int n = 3;
//        int[][] puddles = {{2, 2}};

        int m = 5;
        int n = 6;
        int[][] puddles = {{4, 1}, {1, 3}, {3, 4}, {1, 5}};
        solution(m, n, puddles);
    }
}