프로그래머스 - 등굣길, Cpp

https://programmers.co.kr/learn/courses/30/lessons/42898 

코딩테스트 연습 - 등굣길

- 목표 지점까지 가장 빠르게 도착하는 패스가 몇 개인지 를 물어보는 문제로, 문제 유형이 DP로 이미 공개되어있어서 쉽게 접근할 수 있다.

 

1. 우선 m x n을 row x col 좌표로 두고, 시작점 0,0을 1로 초기화 나머지를 0으로 초기화 한다.

2. puddles이 있는 경우는 -1로 초기화 한다.

3. 문제가 오른쪽과 아래쪽으로만 움직일 수 있기 때문에, 패턴을 단순화 할 수 있다.

row/col	m1	m2
n1	1	0
n2	0	0

DP의 특성상 큰 문제를 작은 문제로 나누어서 생각해 볼 수 있는데,

row를 바깥 루프, col을 안쪽 루프로 이중 for 문을 돌면서 보면

먼저 (0,0)에서 다음 좌표는 오른쪽 또는 아래로 (1,0) 또는 (0,1)이다. 각 좌표로 갈 수 있는 방법은 방금 0,0에서 접근한 한가지 방법 뿐으로 아래처럼 된다.

 

row:0, col:0

row/col	m1	m2
n1	1	1
n2	1	0

그 다음 col인 (0,1)에서 다시 시작해서 다음 좌표를 보면, (1, 1) 이 유일한데

그럼 여기서 (0,1)에서 (1,1)로 접근했으로 (1,1)도 1이다.

row:0, col:1

row/col	m1	m2
n1	1	1
n2	1	1

그 다음 col이 끝났으므로 col을 다시 0으로 초기화 하고 row를 1증가 시키면

 

row:1, col:0

row/col	m1	m2
n1	1	1
n2	1	2

(1,0)에서 다음 좌표는 (1,1)로 갈 수 있는데, 

아까 (0,1)에서 접근해서 이미 (1,1)은 1이다.

여기에 더해서 (1,0)에서 접근할 수 있기 때문에 (1,1)은 최종적으로 2가 된다.

 

여기서 한가지 의문점은, 모든 방법이 그럼 가장 빠른 방법일까 하는 것인데? 본 문제에서 아래-오른쪽 으로만 이동해보면, 도착 거리가 다 똑같다는 것을 알 수 있다. 따라서 앞서 한 작은 문제를 확장시켜 적용하기만 하면 문제는 풀린다.

 

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    const int mod = 1000000007;
    int dp[n][m];
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            dp[r][c] = 0;
        }
    }
    for (int i = 0; i < puddles.size(); i++) {
        dp[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
    }
    
    dp[0][0] = 1;
    int dx[2] = {0, 1};
    int dy[2] = {1, 0};
    
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < m; col++) {
            if (dp[row][col] == -1) { continue; }
            for (int index = 0; index < 2; index++) {
                int nx = row + dx[index];
                int ny = col + dy[index];
                if(nx >= n || ny >= m || (dp[nx][ny] == -1)) { continue; }
                dp[nx][ny] = (dp[row][col] + dp[nx][ny]) % mod;
            }
                
        }
    }
    return dp[n-1][m-1];
}