이번에 풀어본 문제는
프로그래머스 등굣길 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Solution {
    static int [][] map;
    static int M,N;
    static int [] dx = {0,-1};
    static int [] dy = {-1,0};
    public int solution(int m, int n, int[][] puddles) {
        M = m;
        N = n;
        map = new int[N][M];
        for (int [] puddle : puddles) {
            int x = puddle[0] - 1;
            int y = puddle[1] - 1;

            //웅덩이 -1
            map[y][x]--;
        }

        map[0][0] = 1;
        int num = 1_000_000_007;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 웅덩이가 아닐 때
                if (map[i][j] >= 0) {
                    // 좌, 상 더함
                    for (int idx = 0; idx < 2; idx++) {
                        int mx = i + dx[idx];
                        int my = j + dy[idx];
                        if (isValid(mx, my) && map[mx][my] > 0) {
                            map[i][j] += (map[mx][my] % num);
                        }
                    }
                }
            }
        }
        return (map[N - 1][M - 1] % num);
    }
    static boolean isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < M;
    }
}

📝 풀이

물 웅덩이를 피해, 집에서 학교까지 갈 수 있는 경로의 개수를 구하는 문제입니다.
오른쪽이나 아래쪽 두 방향으로의 이동밖에 할 수 없기 때문에, 시작 지점을 1로 초기화 시키고 자신의 인덱스를 기준으로 왼쪽이나 위쪽에서 올 수 있는 경로의 수를 누적하여 더해주면 map[n-1][m-1]에서 결괏값을 확인할 수 있습니다.

📜 후기

최단거리를 구하는 줄 알고 문제 설명으로 주어진 결괏값을 이해하지 못해서 문제를 한참 읽었네요 ..ㅎㅎㅎ