42898. 등굣길

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=java

제한사항 

풀이

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
	    int[][] dp = new int[m+1][n+1];
		int[][] map = new int[m+1][n+1];
		for(int i = 0 ; i< puddles.length; i++) {
			int r = puddles[i][0];
			int c = puddles[i][1];
			map[r][c] = -1;
			}    
	    dp[1][1] = 1;
	    for(int i = 1 ; i <= m ; i++)
		    for(int j = 1; j <= n; j++) {
				if((i== 1 && j ==1) || map[i][j] == -1) continue;

				dp[i][j] = (dp[i][j-1] + dp[i-1][j])  % 1000000007;
				
				
		    }
		answer = dp[m][n];
        return answer;
    }
}

회고

처음에는 단순한 DFS 문제라고 생각했지만, 이 문제는 최단 경로의 길이가 아닌 경우의 수를 구하는 문제이기 때문에 DFS는 시간 복잡도 측면에서 적절하지 않다고 판단했다. 출발지와 목적지가 고정되어 있고, 경로는 항상 오른쪽이나 아래쪽으로만 이동할 수 있기 때문에, 중복 계산을 방지하면서 효율적으로 결과를 구할 수 있는 동적 계획법(DP)을 적용했다.

dp[i][j]는 좌표 (i, j)까지 올 수 있는 경로의 수를 의미하며, 해당 위치가 웅덩이가 아닌 경우, 왼쪽(dp[i][j-1])과 위쪽(dp[i-1][j])에서 오는 경로의 수를 더하여 계산한다. 다만, 웅덩이인 경우는 경로가 될 수 없으므로 제외해야 한다. 즉, 핵심 점화식은 다음과 같다.

• dp[i][j] = dp[i-1][j] + dp[i][j-1] (단, 웅덩이가 아닌 경우)
• 이때 값이 매우 커질 수 있으므로, 매 연산마다 1000000007로 나눈 나머지를 저장했다.

이번 문제를 통해 DP를 경로 문제에 어떻게 활용할 수 있는지를 다시 한 번 복습할 수 있었다.