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

[문제 설명]

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

코딩테스트 연습 - 등굣길

---

[풀이 과정]

DP를 응용하여 푸는 문제이다. 

집에서 학교까지의 좌표가 주어졌을 때 최단경로의 개수를 구하는 방법은 다음 규칙을 이용한다. 

 

m=4, n=3

1) (x, y) = (x+1, y)[아래] + (x, y+1)[오른쪽]

단, (x+1, y), (x, y+1) 좌표가 둘 다 위치범위를 넘어간다면 (x,y)는 1로 초기화 해준다. 

또한 (x+1, y)나 (x, y+1) 중 하나만 위치범위를 넘어간다면 범위내에 있는 좌표값만 더해준다. 

 

2) 물 웅덩이가 있는 좌표를 만났다면 무조건 0으로 초기화한다. 

물 웅덩이가 있는 곳이라면 아예 지나갈수 없는 길이다. 따라서 좌표값을 0으로 설정한다. 

 

3) 모듈러 연산 

모듈러 연산법을 간단하게 써보면 다음과 같다 .

a = (b + c) 라면 다음 식을 만족한다. 

a % m = (b%m + c%m) % m

 

문제에서 최단경로의 개수를 1,000,000,007로 나누라는 조건이 있는데 아마도 답이 Integer 범위값을 넘어가는 것을 방지하고자 한 것 같다. 

따라서 이 문제에서는 (x, y) % 1,000,000,007 를 구하는 것이므로 (x,y) = (x+1, y) + (x, y+1) 를 할때마다 다음과 같이 변경하여 연산해주면 된다. 

(x, y) += (x+1, y) % 1,000,000,007

(x, y) += (x, y+1) % 1,000,000,007;

(x, y) = (x,y) % 1,000,000,007;

 

4) 좌표에 유의!

처음에 문제를 풀 때 m=4, n=3 이면 학교좌표는 (3,4) 일텐데 왜 (4,3)이지? 라고 이상하게 생각했었다(이 부분이 함정이었음)

문제에서는 x,y 좌표를 바꿔서 냈고, 웅덩이 좌표역시 x,y를 바꿔서 제공했다. 

때문에 문제에서 웅덩이의 좌표를 (x,y)라고 했다면 실제 문제를 풀때는 (y,x)를 웅덩이로 풀어야 답이 나온다. 

 

∴느낀점 :

좌표를 거지같이 꼬아놓은 문제에 유의하자. 

그리고 문제를 읽을 때 조금이라도 이상하다고 생각하는 부분이 있다면 그러려니 넘어가는 자세보다는 문제의 함정일 수 있다는 합리적 의심을 반드시 하자. 처음에 넘어간 부분이 함정이었다. 

문제를 읽을 때 어떤 알고리즘을 사용해야하는지 아직 잘 파악하지 못한다. 

문제가 DP 카테고리에 들어가있었으니 망정이지 아니었으면 DP 생각도 못했을 것 같다. 

문제를 보고 사용해야하는 알고리즘이 팍팍 떠오르도록 공부하자. 

---

[JAVA code]

package com.algorithm.programmers.level3;

public class Test05 {
    public static void main(String[] args) {
        int m = 4;
        int n = 3;
        int[][] puddles = {{2, 2}, {3, 3}};

        System.out.println("answer = " + solution(m, n, puddles));
    }

    public static int solution(int m, int n, int[][] puddles) {
        int answer;
        int NUM = 1000000007;

        int[][] locations = new int[n + 1][m + 1];

        int width_length = locations.length;
        int height_length = locations[0].length;
        for (int i = width_length - 1; i >= 0; i--) {
            for (int j = height_length - 1; j >= 0; j--) {

                // 물웅덩이면 0으로 초기화 
                if (isPuddles(i, j, puddles)) {
                    //  System.out.println("(" + i + "," + j + ")" + "is puddles");
                    locations[i][j] = 0;
                    continue;
                }

                // 오른쪽, 아래 모두 범위를 벗어나는 좌표이면 1로 초기화 
                if ((i + 1) >= width_length && (j + 1) >= height_length) {
                    locations[i][j] = 1;
                } else {
                    // 오른쪽 좌표가 범위내에 있다면 더함
                    if ((i + 1) < width_length) {
                        locations[i][j] += (locations[i + 1][j] % NUM);
                    }

                    // 아래쪽 좌표가 범위내에 있다면 더함
                    if ((j + 1) < height_length) {
                        locations[i][j] += (locations[i][j + 1] % NUM);
                    }
                }
                
                // 모둘러 연산
                locations[i][j] = locations[i][j] % NUM;
                // System.out.print("(" + i + "," + j + ")" + "[" + locations[i][j] + "]  ");
            }
            // System.out.println();
        }

        answer = locations[1][1];
        return answer;
    }

    /**
     * 물 웅덩이인지 체크
     * @param x
     * @param y
     * @param puddles
     * @return
     */
    public static boolean isPuddles(int x, int y, int[][] puddles) {
        for (int i = 0; i < puddles.length; i++) {
            int[] array = puddles[i];
            if (array[0] == y && array[1] == x) {
                return true;
            }
        }
        return false;
    }
}