[PS/Java] Programmers - 등굣길

문제	플랫폼	난이도	유형	풀이 링크	문제 링크
등굣길	Programmers	Level 3	DP	풀이	문제

풀이

Case 1: BFS(시간초과)

import java.util.*;

class Solution {
    private int[][] dir = {{0, 1}, {1, 0}};
    private int r, c;
    
    public int solution(int m, int n, int[][] puddles) {
        r = n;
        c = m;
        
        int[][] map = initMap(puddles);
        int numOfMinDist = bfs(map);

        return numOfMinDist % 1000000007;
    }
    
    private int bfs(int[][] map) {

        Queue<Point> q = new LinkedList<>();
        q.add(new Point(1, 1));
        int count = 0;

        while (!q.isEmpty()) {

            int qSize = q.size();

            for (int i = 0; i < qSize; i++) {
                Point cur = q.poll();

                for (int d = 0; d < 2; d++) {
                    int nr = cur.r + dir[d][0];
                    int nc = cur.c + dir[d][1];

                    if(nr == r && nc == c) count += 1;
                    if (!isRange(nr, nc)) continue;

                    if (map[nr][nc] == 1) continue;

                    q.add(new Point(nr, nc));
                }

            }

            if (count > 0) break;
        }

        return count;


    }

    private boolean isRange(int nr, int nc) {
        return nr >= 1 && nr <= r && nc >= 1 && nc <= c;
    }

    private int[][] initMap(int[][] puddles) {
        int[][] map = new int[r + 1][c + 1];

        for (int i = 0; i < puddles.length; i++) {
            map[puddles[i][1]][puddles[i][0]] = 1; // 물에 잠긴 지역 (r, c 주의)
        }

        return map;
    }

    private class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

bfs로 완전탐색하면 팡팡 터집니다.
당연히 문제에 대한 접근이 잘못된 것인데요.
최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하는 이유가 있습니다.

Case 2: DP

import java.util.*;

class Solution {    
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n + 1][m + 1];
        Arrays.stream(puddles).forEach(puddle -> dp[puddle[1]][puddle[0]] = -1);
        dp[1][1] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {

                if (dp[i][j] == -1) { // 침수된 지역
                    dp[i][j] = 0;
                    continue;
                }

                if (i != 1) dp[i][j] += dp[i - 1][j] % 1000000007;
                if (j != 1) dp[i][j] += dp[i][j - 1] % 1000000007;
             }
        }

        return dp[n][m] % 1000000007;
    }

}

각 dp 연산에 1,000,000,007로 나눈 나머지 모듈러 연산을 잊지 말고 같이 해줘야 합니다.

...	x-1	x
y-1	250000001	500000004
y	500000004	?

puddles가 없을 때, n = 100, m = 100의 예제에서,
값이 어느 순간 int를 벗어나며 다음과 같이 나오게 됩니다.

0	...	97	98	99	100
1	...	1	1	1	1
2	...	97	98	99	100
99	...	-1700295972	-540049900	-1080099800	-1064701800
100	...	555447900	15398000	-1064701800	-2129403600

따라서 모듈러 연산을 통해 값을 조절해줘야 합니다.

Case 3: Recursion

import java.util.*;

class Solution {
    private static int[][] map;
    private static int row, col;
    
    public int solution(int m, int n, int[][] puddles) {
        row = n;
        col = m;

        map = new int[n + 1][m + 1];
        Arrays.stream(puddles).forEach(puddle -> map[puddle[1]][puddle[0]] = -1);
        map[n][m] = 1;

        return recursion(1, 1);
    }

    private static int recursion(int r, int c) {
        if (r > row || c > col || map[r][c] < 0) return 0;
        if (map[r][c] > 0) return map[r][c];
        return map[r][c] = (recursion(r, c + 1) + recursion(r + 1, c)) % 1000000007;
    }

}

프로그래머스 질문하기에 있는 김찬정님 풀이를 보고 방향만 (1, 1) -> (n, m)으로 바꿔서 풀어보았습니다.