[JAVA] 프로그래머스 LEVEL3 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

코딩테스트 연습 > 동적계획법(Dynamic Programming) > 등굣길

 

난이도: LEVEL3

알고리즘 유형: DP

풀이 설명

기본적인 DP 문제이다.

LEVEL3 ..?

 

시작 지점: 배열 가장 왼쪽 위 

도착 지점: 배열 가장 오른쪽 아래 

 

요구사항

시작 지점 → 도착 지점까지 최단 거리로 이동하는 경우의 수 구하기 

 

이동하는 방법은 오른쪽 이동 / 아래로 이동 

이건 제한사항 보단 힌트에 가깝다. 

최단 경로로 움직인다고 하면 왼쪽이나 위로 움직이는 경우는 없다. 

이유: 시작 지점과 도착 지점의 위치

 

최단거리 경로 누적은 전형적인 2차원 배열 전체를 2중 for문을 돌리면 된다. 

경로 누적 방식은 현재 좌표에서 행이 1칸 아래인 누적 배열인 DP 값과 (왼쪽 →  오른쪽(현재)

현재 좌표에서 열이 1칸 아래인 누적 배열 DP의 값을 더하면 된다. ( 위 → 아래(현재))

물론 현재 좌표나 더하는 좌표들이 침수지역이면 안 된다.  

+ ArraysOutOfIndex 주의 

정답 코드

import java.util.*;
class Solution {
    static final int FIX = 1000000007;
    static final int PUDDLE = Integer.MAX_VALUE;
    public int solution(int m, int n, int[][] puddles) {
        int [][] DP = new int [n][m];
        for(int i = 0; i < puddles.length; i++){
            DP[puddles[i][1] - 1][puddles[i][0] - 1] = PUDDLE;
        }
        DP[0][0] = 1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(DP[i][j] == PUDDLE) continue;
                // 위에서 
                if(i - 1 >= 0 && DP[i-1][j] != PUDDLE){
                    DP[i][j] += DP[i-1][j];
                }
                // 왼쪽에서 
                if(j - 1 >= 0 && DP[i][j-1] != PUDDLE){
                    DP[i][j] += DP[i][j-1];
                }
                DP[i][j] %= FIX;
            }
        }
        int answer = DP[n-1][m-1] % FIX;
        return answer;
    }
}