문제

Programmers Lv3, 등굣길

핵심

• 집에서 학교까지 갈 수 있는 최단 경로의 개수를 구하는 문제이다. 집은 왼쪽 최상단에 위치하며, 학교는 우측 최하단에 위치한다. 오른쪽과 아래 방향으로만 움직일 수 있다.
• 오른쪽, 아래 방향으로만 움직일 수 있으니, 학교에 도착했다면 해당 거리가 최단 거리임이 보장된다. (어떤 구역을 두 번 거칠 수 없기 때문이다)
• 문제를 보면 재귀적으로 접근하기 좋다. 상향식과 하향식 접근 모두 알아본다.

1. 하향식 접근(메모이제이션)

• 큰 문제를 해결하기 위해 작은 문제로 나누는 방식이다. 이미 해결된 작은 문제는 메모이제이션을 통해 반복 계산을 피한다.
• 먼저 출발지에서 목적지까지의 경로를 찾는다. (큰 문제) 이때, 오른쪽으로 이동하는 경우와 아래쪽으로 이동하는 경우를 재귀적으로 호출한다. (작은 문제) 이때 중복된 계산을 방지하기 위해 memo 배열을 사용할 수 있다.

int goToSchool(int y, int x, int r, int c, int[][] map, int[][] memo) {
	
	if (y >= r || x >= c || map[y][x] == 1)
		return 0;
	
	if (y == r - 1 && x == c - 1)
		return 1;
	
	if (memo[y][x] != -1)
		return memo[y][x];
	
	memo[y][x] = (goToSchool(y + 1, x, r, c, map, memo) + goToSchool(y, x + 1, r, c, map, memo)) % 1_000_000_007;
	
	return memo[y][x];
}

전체 코드

import java.util.*;

class Solution {
    
    public int solution(int m, int n, int[][] puddles) {
        
        int[][] map = new int[n][m];
        int[][] memo = new int[n][m]; 
        
        for (int i = 0; i < puddles.length; ++i) map[puddles[i][1] - 1][puddles[i][0] - 1] = 1;
        
        for (int i = 0; i < n; ++i) Arrays.fill(memo[i], -1);

        return goToSchool(0, 0, n, m, map, memo);
    }
    
    int goToSchool(int y, int x, int r, int c, int[][] map, int[][] memo) {
        
        if (y >= r || x >= c || map[y][x] == 1)
            return 0;
        
        if (y == r - 1 && x == c - 1)
            return 1;
        
        if (memo[y][x] != -1)
            return memo[y][x];
        
        memo[y][x] = (goToSchool(y + 1, x, r, c, map, memo) + goToSchool(y, x + 1, r, c, map, memo)) % 1_000_000_007;
        
        return memo[y][x];
    }
}

2. 상향식 접근

• 작은 문제를 먼저 해결한 다음, 그 결과를 이용해 점차 큰 문제를 해결하는 방식이다.
• 먼저 dp[i][j] 점화식을 세운다. 이는 격자에서 (i, j) 위치까지 도달할 수 있는 경로의 수를 뜻하고, 이는 위쪽과 왼쪽에서 오는 경로의 수를 더하여 구할 수 있다.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

• 인덱스 범위를 고려한다면 아래와 같이 작성할 수 있다.

dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
	for (int j = 0; j < m; ++j) {
		if (dp[i][j] == -1) {
			dp[i][j] = 0;
		} else {
			if (i > 0) {
				dp[i][j] += dp[i - 1][j];
			}
			if (j > 0) {
				dp[i][j] += dp[i][j - 1];
			}
			dp[i][j] %= 1_000_000_007;
		}
	}
}
return dp[n - 1][m - 1];

전체 코드

import java.util.*;

class Solution {
    
    public int solution(int m, int n, int[][] puddles) {
        
        int[][] dp = new int[n][m];
        
        for (int i = 0; i < puddles.length; ++i) dp[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
        
        dp[0][0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (dp[i][j] == -1) {
                    dp[i][j] = 0;
                } else {
                    if (i > 0) {
                        dp[i][j] += dp[i - 1][j];
                    }
                    if (j > 0) {
                        dp[i][j] += dp[i][j - 1];
                    }
                    dp[i][j] %= 1_000_000_007;
                }
            }
        }
        return dp[n - 1][m - 1];
    }
}

시간복잡도

• $O(n * m)$