programmers) 등굣길

프로그래머스 등굣길, DP로 풀기

이번에는 프로그래머스의 등굣길 문제를 풀어보았다.

👉프로그래머스 등굣길 문제

---

문제 설명

집에서 학교까지 가는 길이 격자 형태로 주어진다.

집은 왼쪽 위에 있고, 학교는 오른쪽 아래에 있다.
이동은 오른쪽과 아래쪽으로만 할 수 있다.

중간에 물웅덩이가 있는 칸은 지나갈 수 없다.

이때 집에서 학교까지 갈 수 있는 최단 경로의 개수를 구해야 한다.

단, 경로의 수가 매우 커질 수 있으므로 정답은 1,000,000,007로 나눈 나머지를 반환해야 한다.

---

문제 유형 분류

이 문제는 DP, 동적 계획법 문제이다.

처음에는 DFS로 모든 경로를 탐색하면 되지 않을까 생각했다.

각 칸에서 이동할 수 있는 방향은 최대 두 가지이다.

오른쪽으로 이동
아래쪽으로 이동

그렇기 때문에 DFS로 모든 경로를 탐색할 수도 있다.

하지만 격자의 크기가 커지면 가능한 경로 수가 너무 많아져 시간초과가 날 수 있다.

때문에, 각 칸까지 오는 경로의 수를 저장해두고 재사용하는 DP 방식으로 풀어야 한다.

---

DFS로 풀면 왜 안 될까?

DFS는 가능한 모든 경로를 직접 탐색하는 방식이다.

집에서 학교까지 가려면 총 이동 횟수는 대략 다음과 같다.

오른쪽 이동: m - 1번
아래쪽 이동: n - 1번
총 이동 횟수: m + n - 2번

각 이동마다 오른쪽 또는 아래쪽 두 가지 선택지가 생길 수 있으므로, 단순 DFS로 탐색하면 대략 다음과 같은 시간복잡도가 된다.

DFS 시간복잡도: O(2^(m+n))

정확히는 오른쪽 이동과 아래쪽 이동을 배치하는 조합의 수만큼 경로가 생긴다.

예를 들어 100 x 100 격자라면 오른쪽 99번, 아래쪽 99번을 이동해야 한다.

총 이동 횟수 = 198번
가능한 경로 수 = C(198, 99)

이 값은 엄청나게 크다.

즉, DFS로 모든 경로를 하나씩 탐색하면 시간초과가 날 수밖에 없다.

DFS의 공간복잡도는 재귀 호출 깊이만큼이므로 대략 다음과 같다.

DFS 공간복잡도: O(m + n)

공간복잡도만 보면 괜찮아 보일 수 있지만, 문제는 시간복잡도이다.

가능한 경로 수가 너무 많기 때문에 DFS 완전탐색은 적절하지 않다.

---

입력 범위와 시간 복잡도 판단

등굣길 문제에서 격자의 크기는 최대 100 x 100이다.

DP를 사용하면 모든 칸을 한 번씩만 계산하면 된다.

격자의 세로 길이를 n, 가로 길이를 m이라고 하면 DP의 시간복잡도는 다음과 같다.

DP 시간복잡도: O(n * m)

최대 크기에서도,

100 * 100 = 10,000

칸만 계산하면 되므로 충분히 가능하다.

공간복잡도는 dp 배열과 물웅덩이를 표시하는 배열을 사용하므로 다음과 같다.

DP 공간복잡도: O(n * m)

---

DP 배열의 의미 정하기

DP 문제에서 가장 먼저 해야 할 일은 dp 배열의 의미를 정하는 것이다.

이 문제에서는 다음과 같이 정의했다.

dp[y][x] = 집에서 (y, x) 칸까지 오는 방법의 수

여기서 y는 세로 방향, x는 가로 방향이다.

---

점화식 만들기

등굣길 문제에서는 오른쪽과 아래쪽으로만 이동할 수 있다.

그렇다면 어떤 칸 (y, x)에 도착하기 직전에는 어디에 있었을까?

가능한 경우는 두 가지이다.

위쪽 칸에서 내려오는 경우       → dp[y - 1][x]
왼쪽 칸에서 오른쪽으로 오는 경우 → dp[y][x - 1]

따라서 현재 칸까지 오는 방법의 수는 위쪽 칸까지 오는 방법의 수와 왼쪽 칸까지 오는 방법의 수를 더하면 된다.

dp[y][x] = dp[y - 1][x] + dp[y][x - 1];

단, 현재 칸이 물웅덩이라면 지나갈 수 없으므로 해당 칸은 계산하지 않는다.
물웅덩이 칸의 경로 수는 0으로 보면 된다.

---

왜 dp[1][1] = 1로 시작할까?

처음에는 이 부분이 조금 헷갈렸다.

dp[1][1] = 1;

아직 이동하지 않았는데 왜 1이라고 하는지 의문이 들었다.

하지만 DP에서는 출발점에 서 있는 상태 자체를 경로 1개로 본다.

즉,

집까지 오는 방법 = 처음부터 집에 서 있다 = 1가지

라고 생각하면 된다.

만약 dp[1][1]을 0으로 두면 오른쪽 칸과 아래쪽 칸도 모두 0이 되고, 결국 모든 칸의 값이 0이 되어버린다.

그래서 출발점은 반드시 1로 시작해야 한다.

 

 

---

좌표에서 헷갈렸던 부분

이번 문제에서 가장 헷갈렸던 부분은 puddles 좌표였다.

프로그래머스에서 물웅덩이는 다음과 같이 주어진다.

puddles = [[2, 3]]

이 뜻은 다음과 같다.

x = 2
y = 3

즉, puddles는 [x, y] 순서이다.

하지만 Java 2차원 배열은 보통 다음과 같이 접근한다.

array[행][열]

행은 세로 방향이고, 열은 가로 방향이다.

따라서 Java 배열에서는 다음과 같이 접근해야 한다.

array[y][x]

그래서 물웅덩이를 표시할 때는 아래처럼 해야 한다.

isBlocked[y][x] = true;

처음에는 이 부분을 반대로 작성했다.

isBlocked[x][y] = true;

예제에서는 물웅덩이 좌표가 [2, 2]처럼 x와 y가 같은 경우라서 우연히 맞을 수 있다.

하지만 숨은 테스트에서는 [3, 2], [1, 4]처럼 x와 y가 다른 좌표가 나올 수 있기 때문에 틀리게 된다.

이 문제에서 꼭 기억해야 할 부분은 아래와 같다.

puddles는 [x, y]
Java 배열은 [y][x]

또는 이렇게 외우면 된다.

좌표는 가로 먼저
배열은 세로 먼저

---

나머지 연산을 중간에 해야 하는 이유

문제에서는 정답을 1,000,000,007로 나눈 나머지를 반환하라고 되어 있다.

처음에는 마지막에 한 번만 나누면 되지 않을까 생각했다.

return dp[n][m] % 1000000007;

하지만 이렇게 하면 중간에 계산되는 경로 수가 너무 커져서 int 범위를 넘을 수 있다.

Java의 int는 대략 21억 정도까지만 저장할 수 있다.
경로의 수는 빠르게 커질 수 있으므로, 마지막에 나누기 전에 이미 값이 깨질 수 있다.

그래서 DP 값을 갱신할 때마다 나머지 연산을 해줘야 한다.

dp[y][x] = (dp[y - 1][x] + dp[y][x - 1]) % 1000000007;

나머지 연산에는 다음 성질이 있다.

(a + b) % M = ((a % M) + (b % M)) % M

그래서 중간에 계속 % MOD를 해도 최종 나머지 값은 같다.

 

코딩테스트에서 “정답이 커질 수 있으니 특정 수로 나눈 나머지를 반환하라”는 문장이 나오면,

계산 중간마다 MOD 처리를 해야 한다고 생각하면 된다.

---

내가 최종적으로 작성한 코드

class Solution {
    public int solution(int m, int n, int[][] puddles){
        
        // 문제유형 : DP 
        int answer = 0;
        
        boolean[][] isBlocked = new boolean[n+1][m+1];
        int[][] dp = new int[n+1][m+1];
        
        for(int[] block : puddles) {
            int x = block[0];
            int y = block[1];
            isBlocked[y][x]=true;
        }

        dp[1][1] = 1;

        for (int x1=1; x1<m+1; x1++) {
            for (int y1=1; y1<n+1; y1++) {
                if (!isBlocked[y1][x1] && dp[y1][x1] == 0) {
                    dp[y1][x1] = (dp[y1-1][x1] + dp[y1][x1-1]) % 1000000007;
                 }
            }
        }

        return dp[n][m];
    }
}

---

코드 피드백

위 코드도 통과 가능한 풀이이다.

다만 아래 부분은 꼭 필요하지 않기 때문에 제거 할 수 있다.

 

dp[y1][x1] == 0

각 칸은 반복문에서 한 번씩만 계산되기 때문에, 물웅덩이 여부와 시작점 여부만 명확하게 처리하면 된다.

가독성 측면에서는 x1, y1보다 x, y 또는 row, col처럼 의미가 드러나는 변수명을 쓰는 것이 더 좋다.

---

다듬은 코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        
        int MOD = 1000000007;
        
        boolean[][] isBlocked = new boolean[n + 1][m + 1];
        int[][] dp = new int[n + 1][m + 1];
        
        for (int[] block : puddles) {
            int x = block[0];
            int y = block[1];
            isBlocked[y][x] = true;
        }
        
        dp[1][1] = 1;
        
        for (int y = 1; y <= n; y++) {
            for (int x = 1; x <= m; x++) {
                
                if (x == 1 && y == 1) {
                    continue;
                }
                
                if (isBlocked[y][x]) {
                    continue;
                }
                
                dp[y][x] = (dp[y - 1][x] + dp[y][x - 1]) % MOD;
            }
        }
        
        return dp[n][m];
    }
}

---

시간 복잡도

DP 배열의 모든 칸을 한 번씩 확인한다.

격자의 세로 길이가 n, 가로 길이가 m이므로 시간복잡도는 다음과 같다.

시간복잡도: O(n * m)

물웅덩이를 표시하는 데는 puddles.length만큼 시간이 걸리지만, 전체적으로는 격자를 순회하는 O(n * m)이 핵심이다.

---

공간 복잡도

dp 배열과 isBlocked 배열을 사용했다.

두 배열 모두 크기가 (n + 1) x (m + 1)이다.

따라서 공간복잡도는 다음과 같다.

공간복잡도: O(n * m)

---

복잡도 정리

DFS 시간복잡도: O(2^(m+n))
DFS 공간복잡도: O(m+n)

DP 시간복잡도: O(n * m)
DP 공간복잡도: O(n * m)

이 문제에서는 경로를 모두 직접 탐색하는 DFS보다, 각 칸까지 오는 경로 수를 저장해두는 DP가 적절하다.

---

이번 풀이에서 배운 점

이번 문제는 DP 점화식을 세우는 연습이 되는 문제였다.

가장 중요한 것은 dp[y][x]가 무엇을 의미하는지 먼저 정하는 것이었다.

dp[y][x] = 집에서 (y, x)까지 오는 방법의 수

이 의미를 정하니 현재 칸은 위쪽 칸과 왼쪽 칸에서 올 수 있다는 점을 떠올릴 수 있었다.

그래서 점화식은 아래처럼 만들 수 있었다.

dp[y][x] = dp[y - 1][x] + dp[y][x - 1];

또 이번 문제를 통해 좌표와 배열 인덱스의 차이도 다시 정리할 수 있었다.

puddles는 [x, y]
Java 배열은 [y][x]

이 부분은 정말 헷갈렸고, 예제만 보고는 실수를 찾기 어려웠다.

마지막으로 정답을 특정 수로 나눈 나머지를 반환해야 하는 경우에는 계산 마지막에만 나누는 것이 아니라, 중간 계산마다 % MOD를 해줘야 한다는 것도 배웠다.

---

셀프 체크

왜 처음에 바로 풀지 못했는가?

DFS로 모든 경로를 탐색하면 될 것 같았지만, 입력 크기를 생각하면 시간초과가 날 수 있었다.

그래서 DP로 전환해야 했다.

또 DP 점화식을 세우는 과정이 아직 익숙하지 않았다.

시간이 부족했는가?

문제를 푸는 데 시간 자체가 부족했다기보다, 좌표 처리와 점화식을 이해하는 데 시간이 걸렸다.

문제 해석을 잘못했는가?

이동 방향이 오른쪽과 아래쪽뿐이라는 점은 이해했지만, puddles 좌표가 [x, y]로 주어지고 Java 배열은 [y][x]로 접근해야 한다는 점을 처음에 잘못 처리했다.

자료구조 선택을 잘못했는가?

처음에는 DFS를 생각했지만, 최종적으로는 DP 배열과 물웅덩이 체크용 boolean 배열을 사용했다.

이 문제에서는 DP 선택이 적절했다.

엣지 케이스를 놓쳤는가?

채점 전 코드 테스트시 주어진 입력 값처럼 물웅덩이 좌표가 [2, 2]처럼 x와 y가 같으면 실수가 드러나지 않는다.

하지만 [3, 2]처럼 x와 y가 다른 경우에는 isBlocked[x][y]로 저장하면 틀린 위치가 막힌다.

또 시작점 dp[1][1] = 1을 따로 설정해야 한다는 점도 중요했다.

구현 실수가 있었는가?

처음에는 isBlocked[x][y]로 작성해서 물웅덩이 위치가 잘못 표시되었다.

또 나머지 연산을 마지막에만 하려고 했는데, 중간 계산에서 오버플로우가 날 수 있으므로 매번 % MOD를 적용해야 했다.

시간 복잡도 판단을 잘못했는가?

처음에는 DFS도 가능할지 고민했지만, 모든 경로를 탐색하면 경우의 수가 너무 많아질 수 있다.

DP로 풀면 모든 칸을 한 번씩만 계산하므로 O(n * m)에 해결할 수 있다.