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

문제 링크

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

코딩테스트 연습 - 등굣길

 

흡사 어렸을 적 수학 올림피아드(?)에서 볼 수 있을 법한 느낌의 문제다. (뭔가 낯이 익다..)

이 문제 역시 다이나믹 프로그래밍을 이용하여 쉽게 풀 수 있다.

 

문제의 제한사항처럼 움직일 수 있는 방향은 '오른쪽'과 '아래' 뿐이다. 따라서 해당 방향만 고려해서 풀이하면 된다.

 

그림과 함께 로직을 살펴보자.

 

풀이 방법

 

 

 

(0, 1)을 기준으로, 해당 칸에 올 수 있는 방법은 왼쪽(집)에서 오는 방향 뿐이다. 위에서는 올 수 없다. 

 

 

따라서 해당 칸에는 가짓수 1이 들어간다.

이는 (0, 2) (0, 3)과 (1, 1) (1, 2)도 마찬가지다. (앞의 두 경우는 왼쪽에서밖에 못오고, 뒤의 두 경우는 위에서 밖에 내려오지 못한다.)

 

 

 

 

 

 

 

 

 

(1, 1)기준에서는 위와 왼쪽에서 진입할 수 있다. 

 

둘의 가짓수를 더해 1 + 1 = 2가 된다.

 

 

 

 

 

 

 

 

(1, 2)의 경우, 윗쪽 (0, 2)와 (1, 1)의 횟수를 더한다.

 

즉, 오른쪽+오른쪽

경로를 가진 (0, 2)와

오른쪽+아래, 아래+오른쪽

두 경로를 가진 (1, 1)

 

세 가지 경로수가 (1, 2)에 합쳐지는 것이다.

 

 

 

 

 

이런 규칙대로 칸을 차례대로 채우면 왼쪽과 같다.

 

 

(1, 3)까지 오는 경로의 가짓 수는 4.

 

(2, 2)까지 오는 경로의 가짓 수는 6.

 

두 가짓수를 더한 10이 총 경로의 갯수가 된다.

 

 

 

 

 

다만, 이 문제에는 '웅덩이'가 추가되기 때문에 해당 칸이 웅덩이인 경우는 연산하지 않도록 따로 처리를 해줘야 한다!

 

 

코드 풀이

 

//가는 경우의 수 : 오른쪽 한칸, 아래 한칸
//현재 내 타일 (1, 0)일 때, 바로 전에서 올 수 있는 경로는 (0,0) 하나뿐. dp[1][0] = 1
//(1, 2)일 때, 이전 (1,1)과 (0,2)에서 올수 있는 경로를 더한다. dp[1][2] = dp[1][1] + dp[0][2];
//다만 웅덩이인 경우는 -1 넣고 제외
class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int [][]dp = new int[n][m];
        
        for (int[] i : puddles)
            dp[i[1] - 1][i[0] - 1] = -1;
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dp[i][j] == 0) {
                    if (i != 0 && dp[i - 1][j] != -1)
                        dp[i][j] += dp[i - 1][j];
                    if (j != 0 && dp[i][j - 1] != -1)
                        dp[i][j] += dp[i][j - 1];
                    dp[i][j] %= 1000000007;
                }
            }
        }
        return dp[n - 1][m - 1];
    }
}

 

혹시 같은 로직인데도 테스트 케이스 오류가 뜨는가? 그럼 m과 n을 잘 살펴보자.. 기본적으로 먼저 오는 수를 행, 뒤의 수를 열로 계산하는데, 이 문제는 기본적인 행과 열이 뒤바껴있다. 이 점을 유의해서 풀도록...

(필자는 이 부분때문에 시간을 조금 뺏겼다 ^_ㅜ)