문제 개요 #

• Source: 프로그래머스 문제 링크
• Difficulty: Lv 3
• Key Concept: DP

접근 방법 #

동적 계획법을 이용하여 Top Down 방식으로 원하는 가로 $m$, 세로 $n$ 위치의 최단 거리 이동 경우의 수는 $m-1, n$ 그리고 $n-1, m$을 모두 각각 더하여 구하였습니다. 이를 계속 반복하여 $m-1, n$은 $(m-1)-1, n$ 그리고 $m-1, n-1$의 최단 거리 이동 경우의 수를 더하는 방식으로 재귀를 만들었습니다. 조건의 경우 배열의 범위를 벗어나거나, 해당 좌표가 물웅덩이라면 해당 좌표에선 올 수 없으므로 0을 리턴하도록 하였습니다. 조건을 통과한 다음 해당 좌표의 이동 경우의 수가 이미 저장되어 있다면 메모이제이션을 통해 바로 해당 값을 리턴하도록 하였습니다. 마지막으로 처음 위치에서 오른쪽으로 한 칸 이동한 좌표, 아래로 한 칸 이동한 좌표에 각각 1을 넣어 주어 실제 이동 경로가 연산될 수 있도록 하였습니다.

시행착오 #

초기 접근 방법을 통해 Top down 방식으로 재귀 함수를 생성, 물웅덩이까지 모두 함수를 통해 구현하였습니다. 논리적으로는 문제가 없었지만, 효율성 테스트에서 모든 테스트가 시간 초과가 되어 처음 사용하였던 타입 map의 문제가 있음을 직감하였습니다. map은 Red Black tree 알고리즘을 이용하여 키를 탐색하는데 배열의 크기가 가로세로 최대 100을 넘지 않기 때문에 많은 오버헤드를 불러일으키고 있었습니다. 따라서 vector 타입을 이용하여 좌표별 최단 거리 이동 경우의 수를 저장하는 방식으로 변경하여 정답을 구할 수 있었습니다.

해결 방법 #

#include <vector>

using std::vector;

int width,height;
const int MOD = 1000000007;

vector<vector<int>> dp;

int getPosition(int y, int x){ // O(2*(N+M))
    if(y >= height || y < 0){ // 범위를 벗어난 높이
        return 0;
    }if(x >= width || x < 0){ // 범위를 벗어난 너비
        return 0;
    }if(dp[y][x] == -1){ // 물 웅덩이인 경우
        return 0;
    }
	// 메모이제이션
   	int& ret = dp[y][x];
    if(ret){
        return ret;
    }

    return ret = ((getPosition(y-1,x) % MOD) + (getPosition(y,x-1) % MOD)) % MOD; // 최단거리로 상, 좌에서 내려왔을 때 각각 최단거리의 수
}

void setPuddles(const vector<vector<int>>& puddles){ // O(N*2)
    for(const auto& puddle: puddles){
        if(puddle.size() != 2) {continue;}
        int x = puddle[0] - 1;
        int y = puddle[1] - 1;
        dp[y][x] = -1;
    }
}


int solution(int m, int n, vector<vector<int>> puddles) {
    width = m--;
    height = n--;
    dp.assign(height,vector<int>(width));
    // 초기화 우선
    dp[0][1] = 1;
    dp[1][0] = 1;
    setPuddles(puddles); // 조건 적용
    return getPosition(n,m);
}

알고리즘 설명 #

벡터를 이용해서 입력받은 높이, 너비에 맞게 할당을 한 다음 DP를 이용하여 원하는 좌표로 갈 수 있는 최단거리 이동 경우의 수를 구하였습니다.

dp는 $(y,x)$좌표로 갈 수 있는 최단거리 경우의 수를 의미합니다. 먼저 이동 방향은 오른쪽과 밑 쪽으로만 갈 수 있다고 제약되어 있으니 dp[0][1]과 dp[1][0]의 값을 1로 변경합니다. 이는 초기 위치 $(0,0)$에서 처음 움직인다면 갈 수 있는 좌표값들이며 오직 경우의 수가 1인 좌표들입니다. 그리고 물 웅덩이는 건너갈 수 없으므로 puddles에 기록되어 있는 좌표들은 dp에서 -1로 변경하여 이동할 수 없음을 표시합니다.

Top Down 방식으로 재귀 함수를 작성하였고 로직은 원하는 칸에 도달할 수 있었던 좌표, 즉 우, 하방향으로만 이동이 가능했으므로 이 전 단계에서 위치할 수 있는 좌표는 현재 위의 위쪽과 왼쪽 좌표가 됩니다. 그러므로 현재 좌표의 최단거리 경우의 수는 $\text{(왼쪽 좌표의 최단거리 경우의 수) + (위쪽 좌표 최단거리의 경우의 수)}$가 되게 됩니다. 문제의 조건에서 1,000,000,007로 나눈 뒤의 나머지값을 리턴하라는 조건이 있으므로 Modulo 연산의 성질¹을 이용하여 int 값 범위 안에서도 모든 로직이 가능하였습니다.

이렇게 로직을 짜고 난 다음 base condition의 경우 배열의 범위가 0 미만, 높이와 너비 이상인 경우 모두 0으로 리턴시켰습니다. 이후 이미 DP에 계산된 값들의 경우 또 재귀적인 로직이 필요하지 않으므로 메모이제이션을 이용, 바로 DP에서 해당 좌푯값을 꺼내 리턴하였습니다.

성능 분석 #

• Time Complexity: $O(m×n)$
• Space Complexity: $O(m×n)$

핵심 정리 #

동적 계획법에 대한 개념과 모듈로 연산 성질을 알고 있는지에 대한 문제였습니다. 또한 이 문제를 통해 map과 vector에의 탐색 속도에 대해서 더 알 수 있었고 특히 map의 경우는 red black tree를 통해 탐색, vector는 $O(1)$ 시간에 원소를 찾아 잦은 원소 탐색이 있는 로직에서는 vector를 사용해야 함을 알 수 있었습니다.

참고자료 #