[프로그래머스 고득점 kit]동적계획법 Level3 등굣길

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.

  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.

• 물에 잠긴 지역은 0개 이상 10개 이하입니다.

• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

m

n

puddles

return

4

3

[[2, 2]]

4

입출력 예 설명

 

 

접근 방법

등굣길 문제를 풀면서 2번 정도 사고가 막혀서 문제를 풀지 못했었다.

 

1. 최단 거리에 집중하여 넓이 우선 탐색(BFS) 방식을 사용하였다.

 

[1,1]에서 부터 노드를 확장하며 Binary Tree를 그려보니 최단거리로 경로를 구할 수 있을 것 같았다. 

 

결과적으로 정확도 테스트 8번 테스트 케이스에서 시간이 초과하였다.

 

2. 동적계획법에 집중하여 점화식을 구한다.

 

처음에는 m*n 전체 사각형에 대해서 2*1 .... m*n으로 규칙을 찾으려 애썼지만 규칙성을 찾을 수 없었다. 따라서 각 셀에 대해서 규칙성을 찾으려 시도하였다.

 

현재 셀을 [r, c]라고 했을 때 셀의 값은 어떻게 이루어질까(오른쪽, 아래쪽만 이동 가능)?

 

[1, 1]은 집의 위치이기 때문에 1이다

[1, 2]는 [1, 1]에서 한 칸만 내려온 것이기 때문에 [1, 1]의 값과 동일하다.

[2, 1]는 [1, 1]에서 오른쪽 한 칸만 이동한 것이기 때문에 [1, 1]의 값과 동일하다.

[2, 2]는 [1, 2]에서 오른쪽으로 한 칸 이동한 것이다. 그리고 [2, 1]에서 아래로 한 칸 이동한 것이다. 따라서 [1, 2]에서의 값과 [2, 1]의 값을 더해야 할 것이다.

[2, 2] = [1, 2] + [2, 1]

 

만일 [2, 2]가 웅덩이일 경우는 0이 되어야 한다.

 

일반화를 하면 아래와 같다.

 

[r, c] = [r-1, c] + [r, c-1] ([r, c] != 웅덩이)

[r, c] = 0 ([r, c] == 웅덩이)

 

 

한 가지 의문이 들 수 있다. [r-1, c]나 [r, c-1]이 웅덩이일 경우는 어떻게 처리할까??

 

나도 이 부분에 대해서 의문을 가져 고민해보았다. 그 결과 [r-1, c]와 [r, c-1]은 반드시 [r, c] 이전에 나타나기 때문에 웅덩이였을 경우 이미 0으로 처리됐을 것이다. 따라서 위 점화식의 이전 노드가 웅덩이일 경우는 고려하지 않아도 된다.

 

 

위 알고리즘을 구현했지만 정확도는 모두 통과한 반면 효율성은 모두 통과하지 못했다. 

 

그 이유를 보니 위 문제에서 overflow를 고려하여 1,000,000,007을 나눈 나머지를 반환하라고 했었는데, 최종 반환 값에만 나머지 연산을 할 것이 아니라 문제를 푸는 과정에서도 overflow가 발생할 수 있기 때문에 [r, c] 값을 구할 때도 나머지 연산을 적용했어야 했다.

 

소스 코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] map = new int[n+1][m+1];
        for(int[] puddle : puddles){
            map[puddle[1]][puddle[0]] = -1;
        }
        map[1][1] = 1;
        for(int r=1;r<=n;r++){
            for(int c=1;c<=m;c++){
                if(r==1 && c==1) continue;
                int above = map[r][c] == -1 ? 0 : map[r-1][c];
                int before = map[r][c] == -1 ? 0 : map[r][c-1];
                
                map[r][c] = (above + before) % 1000000007;
            }
        }
        return map[n][m] % 1000000007;
    }
}