[프로그래머스 | Java Lv.3] 등굣길 (DP, 동적 프로그래밍)

문제

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

프로그래머스

 

---

접근

 

초등학생 때 풀었떤 문제인데.. 그냥 4*3 - (2*2) 해서 4 아닌가? 

전체 경우의 수 - 웅덩이를 지나서 도착하는 경우의 수

 

먼저 오른쪽과 아래쪽으로만 움직일 수 있으므로 좌표로 표현하면

(x,y) -> (x+1, y) 또는 (x, y+1)

 

규칙을 찾아내서 점화식을 세우자 - DP

map[i][j] = map[i-1][j] + map[i][j-1]

 

어떤 블록까지 가는 최단 거리의 경우의 수는 왼쪽에 있는 경우의 수와 위에 있는 경우의 수의 합이다. 그 두 방면에서부터 올 수 있으니

 

이런 식으로 경우의 수를 구해주면 되는데, 물웅덩이를 고려해서 물웅덩이인 경우 합해주지 않는 식으로 코드를 짜면 된다

---

첫번째 제출 - 실패 

package week5.baek.dp;

public class Ex3 {
    public static int solution(int m, int n, int[][] puddles) {
        int mod = 1000000007;
        int[][] map = new int[n][m];
		
        // 테두리는 경우의 수가 1이니 1로 초기화 -> 이후 문제 됐던 코드
        for (int i = 0; i < m; i++) {
            map[0][i] = 1;
        }
        
        for (int i = 0; i < n; i++) {
            map[i][0] = 1;
        }
		
        //웅덩이는 -1로 초기화
        for(int[] i : puddles){
            map[i[1]-1][i[0]-1] = -1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if(map[i][j] == -1) continue; //웅덩이면 PASS
                else if(map[i-1][j] == -1 && map[i][j-1] == -1) map[i][j] = 0;
                else if(map[i-1][j] == -1) map[i][j] = map[i][j-1];
                else if(map[i][j-1] == -1) map[i][j] = map[i-1][j];
                else map[i][j] = (map[i-1][j] + map[i][j-1]) % mod;

            }
        }


        return map[n-1][m-1];
    }

    public static void main(String[] args) {
        int[][] puddles = {{2,2}};
        System.out.println(solution(4,3,puddles));
    }
}

 

문제점 1 

m과 n의 순서가 틀렸다

 

문제점 2

https://school.programmers.co.kr/questions/15829

태홍님 감사합니다..

 

나는 X좌표가 0이거나 Y좌표가 0인 점들은 모두 경우의 수가 1이라서 1로 초기화를 먼저 시켰다. 

하지만 이렇게 풀었을 경우 반례가 있었다

 

위 태홍님 글을 보면 [0,1]. [1,0]이 웅덩이로 주어졌다면, 등굣길이 사방이 막혔기 때문에 경우의 수는 0이 되어야하는데, 1로 테두리를 초기화 하면 그게 무시되고 계산이 된다. 

 

최종 코드

package week5.baek.dp;

public class Ex3 {
    public static int solution(int m, int n, int[][] puddles) {
        int mod = 1000000007;
        int[][] map = new int[n][m];

        map[0][0] = 1;

        for(int[] i : puddles){
            map[i[1]-1][i[0]-1] = -1;
        }

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


        return map[n-1][m-1];
    }

    public static void main(String[] args) {
        int[][] puddles = {{2,2}};
        System.out.println(solution(4,3,puddles));
    }
}

---

참고

https://moonsbeen.tistory.com/75

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