[프로그래머스] 등굣길 문제 - DP 재귀로 풀어야 쉽다

박감자·2025년 9월 23일

[프로그래머스] 등굣길 문제 - 재귀적 DP 풀이 (Top-Down 방식)

문제 소개

프로그래머스 고득점 Kit의 DP 문제인 등굣길은 m x n 격자에서 왼쪽 위(집)에서 오른쪽 아래(학교)까지 가는 경우의 수를 구하는 문제입니다. 단, 특정 칸(puddles)은 물웅덩이로 막혀 있어 지나갈 수 없습니다.

시작점: (1, 1)
도착점: (m, n)
이동 방식: 오른쪽, 아래쪽으로만 이동 가능
출력: 경우의 수 % 1,000,000,007

제한사항

격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
물에 잠긴 지역은 0개 이상 10개 이하입니다.
집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

자세한 문제 설명: https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=javascript

접근 방식

보통 이 문제는 DP 테이블을 채우는 Bottom-Up 방식으로 많이 푸는 것 같은데 Top-Down 메모이제이션 방법으로도 풀어보았다.

"현재 위치에서 오른쪽과 아래쪽으로 가는 경우의 수를 더하면 된다"를 재귀적으로 구현한 것이다.

DP induction (재귀적 접근)

DP 결국 문제를 작게 쪼개서 반복되는 연산을 줄이는 방법이라고 생각한다.
그렇다면 이 문제는 어떻게 쪼갤 수 있는가??

우선 이 문제는 가는 방향이 2개로 제한되어있다. 그리고 시작점은 항상 왼쪽 위, 도착 점은 오른쪽 아래로 정해져있다.
그래서 아래와 같은 패턴이 반복되는 것을 볼 수 있다.

예) [2, 3]인 m, n이 주어졌을때

시작점에서
오른쪽으로 -> 거리 1 + [1, 3]인 m, n의 최종 거리
아래로 -> 거리 1 + [2, 2]인 m, n의 최종 거리

[1, 3]의 시작점에서
오른쪽으로 -> 거리 1 + [0, 3]인 m, n의 최종 거리
아래로 -> 거리 1 + [1, 2]인 m, n의 최종 거리

[2, 2]의 시작점에서
오른쪽으로 -> 거리 1 + [1, 2]인 m, n의 최종 거리
아래로 -> 거리 1 + [2, 1]인 m, n의 최종 거리

~~(그래프를 말로 설명하는 건 고역이군...)~~

즉, 이동할수록 더 작은 좌표를 이동해야하는 문제로 볼 수 있다.
최종적으로는 아래의 그래프와 같다.

위 그래브페어 리프 노드의 특징 (마지막 자식 노드)는
1) m = 1, n = 1인경우
2) m = 0 혹은 n = 0인 경우 [존재하지 않는 좌표]

그리고 결국 부모 노드는 자식 노드의 합과 같은 것이다.
좌표가 0인 노드는 0을 반환할거고
둘다 1인 노드는 1을 반환한다

그래서 (1, 2)는 시작에서 도착까지 가는 거리가 0 + 1 = 1
(2, 1)은 시작에서 도착까지 가는 거리가 1 + 0 = 1
>> 둘을 합치면 (2, 2) 는 2개의 방법

(1, 3)도 마찬가지로 계산하면 0 + 1 = 1
>> 따라서 (2, 3) 모든 경우의는 (1, 3) + (2, 2) = 1 + 2 = 3이다

그렇다면 우리는 아래와 같은 방법을 구현할 수 있다.

1차 코드 (only 재귀)

function solution(m, n) {
  	// 이건 문제에서 해당 값으로 나눈 나머지를 반환하기 때문에 만든 상수
    const MOD = 1_000_000_007;		
  
    const top_down = (x, y) => {
        // (1,1)에 도착하면 경로 1개 완성
        if (x === 1 && y === 1) return 1;
        // 격자 밖으로 벗어난 경우
        if (x === 0 || y === 0) return 0;
        
        // 오른쪽으로, 아래쪽으로 이동 경우 합산
		return top_down(x - 1, y) + top_down(x, y - 1) % MOD;
    }
    
    return top_down(m, n);
}

1차 개선

자 그럼 이 코드가 잘 통과 되나요?
-> 아뇨, 시간 초과가 떠요

위의 코드는 $O(2^{n+m})$ 의 시간 복잡도를 가지는데, 첨부한 이미지와 비교한다면 끔찍한 빨간색에 속한다는 것을 알 수 있다

이때 활용되는 것이 Memoization(메모이제이션) 이다!

메모이제이션

동일한 연산을 줄이기 위해 이전의 값을 저장하는 방법

그래프를 다시 보자 이 경우 반복적인 계산들이 보인다

그래프가 더 커진다면 반복적인 연산도 늘어난다.

JS에서 $O(1)$ 의 방법으로 결과를 꺼내올 수 있는 객체는 Object{}라 이를 활용하는 방향으로 코드를 정리하면
(1,2) 라는 값을 키의 형태로 만들고 값을 1이라고 저장한다면!!

const memo = {
	"1,2": 1 
}

감을 잡아가고 있다. 쉼표는 넣어주어야 "m,n"으로 잘 표현 된다.
"574"라고만 하면 (57, 4)인지 (5, 47)인지 구분이 안된다

추가할 스탭

연산하고자 하는 좌표값이 이미 존재한다면 연산한 값을 반환하자
새로 연산된 값이라면 저장!을 해주자

그럼 memo를 넣어 시간 복잡도를 줄여보자

2차 코드 (재귀와 메모이제이션)

function solution(m, n) {
    const MOD = 1_000_000_007;
  	// 연산값을 저장할 Object
  	const memo = {};
  
    const dp_top_down = (x, y) => {
        if (x === 1 && y === 1) return 1;
        if (x === 0 || y === 0) return 0;
      
      	// 저장을 위해 특수 키를 만들어주자!
      	const key = `${x},${y}`;
        
        // 추가된 스탭: 메모이제이션 확인
        if (key in memo) return memo[key];
        
        // 저장! 오른쪽 + 아래쪽 경로 수를 합산하여 
        memo[key] = (dp_top_down(x - 1, y) + dp_top_down(x, y - 1)) % MOD;
        return memo[key];
    }
    
    dp_top_down(m, n);
    // 연산된 값만 반환
    return memo[`${m},${n}`];
}

2차 개선

자, 그럼 시간 복잡도도 잡았겠다, 문제 답 통과 되나?
-> 아뇨, 문제를 읽으면 물웅덩이가 존재한다는 것을 알 수 있다.

여기서 반전
참조한 문제가 아니라 프로그래머스 문제를 들고 왔지

이 문제는 물웅덩이가 있다구!!!
>> 그냥 물웅덩이만 피하면 된다

단, 주어지는 puddles는 2차원 배열이므로
이를 Set()로 변형하여 참조 시간 복잡도를 O(1)로 줄이는 과정을 추가만 한다면
물웅덩이는 금방 피할 수 있다.

추가할 스탭

puddles를 Set로 만들어준다 (이때 memo와 동일한 키를 쓰자)
웅덩이가 있는 좌표인지 확인하는 스탭을 추가하고 이때 웅덩이는 지나갈 수 없으니 0 반환

완성 코드

function solution(m, n, puddles) {
    const MOD = 1_000_000_007;
  	// Set으로 변환
    const puddlesSet = new Set(puddles.map(puddle => `${puddle[0]},${puddle[1]}`));
    const memo = {};
    
    const dp_top_down = (x, y) => {
        if (x === 1 && y === 1) return 1;
        if (x === 0 || y === 0) return 0;
        
        const key = `${x},${y}`;
        if (key in memo) return memo[key];
        // 물웅덩이 칸이면 갈 수 없음
        if (puddlesSet.has(key)) return 0;
        
        memo[key] = (dp_top_down(x - 1, y) + dp_top_down(x, y - 1)) % MOD;
        return memo[key];
    }
    
    dp_top_down(m, n)
    return memo[`${m},${n}`];
}

핵심 포인트

메모이제이션(memo 객체) 활용
- 동일한 좌표를 여러 번 계산하지 않도록 memo에 저장
- 시간복잡도를 O(m*n) 수준으로 줄임
Set으로 물웅덩이 관리
- puddles 배열을 바로 쓰는 대신 Set으로 변환하여 O(1) 시간에 체크
Top-Down 방식의 직관성
- "학교 (m, n)까지 오는 경로 수 = (왼쪽에서 오는 경로 수) + (위쪽에서 오는 경로 수)"라는 직관을 그대로 코드로 표현

Bottom-Up 방식과 비교

Top-Down
- 직관적이고 재귀 호출로 쉽게 이해할 수 있음.
- 단, 재귀 호출 스택 때문에 입력이 큰 경우 주의가 필요.
Bottom-Up
- 반복문으로 테이블을 채워나가므로 스택 오버플로우 위험 없음.
- 하지만 직관적으로는 다소 딱딱한 구현이 될 수 있음.

즉, 학습용/아이디어 확인용으로는 Top-Down이 더 이해하기 쉽고, 실무적으로는 Bottom-Up이 안정적이라고 볼 수 있다.
각각 상황에 맞게 해결해보는 연습을 해보자