프로그래머스 DP 등굣길 Java

계속 몇 가지 테스트 케이스만 틀렸었어서 열받아서 고치고 질문 확인하고 구글링하다가 푼 문제... 

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

프로그래머스

 

- 기본적으로 맨 위 가로줄, 맨 왼쪽 세로줄을 다 1로 채워주고 웅덩이를 -1 처리해서 계산했었다. 

- 한 좌표의 값을 구하는 것은 해당좌표 왼쪽과 위쪽을 기준으로 합쳐서 계산하는데, 왼쪽과 위 모두 웅덩이면 못가는 걸로 처리.. 

- 한쪽만 웅덩이면 Math.max로 그대로 값을 가져왔었다. 

 

->  가장자리에 웅덩이가 있는경우 그 방향으로는 진행을 못한다. 위 논리대로 짜면 그 부분에서 오류가 나서 몇몇 테스트케이스를 통과하지 못했다 (프로그래머스 질문하기 보고 깨달음)

-> 따라서 아래코드처럼 맨 위 가로줄, 맨 왼쪽 세로줄을 1로 채워줄 때 웅덩이 있는지 없는지 여부를 검사해서, 있다면 -1로 값을 넣어준다(그방향으로 진행 못하게끔)

for (int i = 1; i < n; i++) {
            if (map[i-1][0] != -1 && map[i][0] != -1) {
            	// 나도 웅덩이 아니고, 내 앞에 있던 애도 웅덩이 아니어야 함 
                map[i][0] = 1;
            }
            else {
                map[i][0] = -1;
            }
}

 

-> 이차원 배열 가로가 2칸 세로가 4칸이라면 선언 시 int [4][2] 이렇게 한다. 좌표는 아래 표와 같음

-> 아래 표는 행(row) 4, 열(col) 2이다. row와 col로 들어왔다면 int[row][col]이렇게 해도 되는데 가로세로 사이즈로 매개변수를 줘서;;; 

(0,0)	(0, 1)
(1, 0)	(1, 1)
(2, 0)	(2, 1)
(3,0)	(3,1)

-> 이 문제에서는 m이 가로, n이 세로로 들어왔다. 즉 int[n][m]으로 선언해줘야한다

-> 웅덩이 좌표도 그래서 반대로 넣어줘야 한다...

 

 

💧진행방향이 오른쪽, 아래쪽만 가능하므로 각 칸은 왼쪽과 위쪽을 기준으로 계산하게 된다. 

- 둘중 하나만 웅덩이면 max값으로, 둘다 웅덩이면 -1로, 둘다 웅덩이 아니면 (왼쪽 + 위) % NUM하기 

- NUM = 1000000007 (문제에서 주어진 조건) 

 

class Solution {
    public static int NUM = 1000000007;
    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n][m];
        // n이 x좌표 m이 y좌표

        for (int i = 0; i < puddles.length; i++) {
            int x = puddles[i][0] - 1;
            int y = puddles[i][1] - 1;
            map[y][x] = -1; // 웅덩이 표시 
        }
        
        for (int i = 1; i < n; i++) {
            if (map[i-1][0] != -1 && map[i][0] != -1) {
                map[i][0] = 1;
            }
            else {
                map[i][0] = -1;
            }
        }
        
        for (int i = 1; i < m; i++) {
            if (map[0][i-1] != -1 && map[0][i] != -1) {
                map[0][i] = 1;
            }
            else {
                map[0][i] = -1;
            }
        }
        
        
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (map[i][j] != -1) {
                    int a = map[i-1][j];
                    int b = map[i][j-1];
                
                	// 둘 다 웅덩이 
                    if (a == -1 && b == -1) {
                        map[i][j] = -1;
                    } 
                    else {
                        if (a == -1 || b == -1) {
                        	// 둘 중 하나만 웅덩이
                            map[i][j] = Math.max(a, b);
                        }
                        else {
                            map[i][j] = (a + b) % NUM;
                        }
                        
                    }
                }
            }
        }
        
        return map[n-1][m-1] == -1 ? 0 : map[n-1][m-1];
    }
}