보행자 천국 [Lv. 3]

프로그래머스

M * N 크기의 격자 모양 배열이 있을 때, 좌표 (0,0)에서 좌표(m-1,n-1) 까지 이동할 수 있는 경로의 수를 구하여라.

1. 아래, 오른쪽으로만 이동할 수 있음

2. 직진만 가능한 구간이 있음

3. 진입이 불가능한 구간이 있음

 

풀이 방법

모든 구간이 이동 가능하다고 할때의 풀이법부터 생각해보자.

0,0 구간으로 이동 할 수있는 경우의 수는 무조건 1개이다.

 

(0,1) , (1,0)은 (0,0)만을 통해 이동할 수 있으니 경우의 수가 1이다.

 

(0,2)는 (0,1)을 통해서만 이동이 가능하니 1

(2,0)은 (1,0)을 통해서만 이동이 가능하니 1

(1,1)은 (0,1), (1,0)을 통해서 이동이 가능하니 그들의 경우의 수를 더해서 2

 

(1,2)는 (0,2), (1,1)을 통해서 이동이 가능하니 그들의 경우의 수를 더해서 3

(2,1)은 (2,0), (1,1)을 통해서 이동이 가능하니 그들의 경우의 수를 더해서 3

 

마지막 (2,2)는 (2,1), (1,2) 를 통해서 이동이 가능하니 그들의 경우의 수를 더해서 6이 나옵니다.

코드로 표현하자면 아래와 같습니다.

if (i < m)
	dp[i+1][j] += dp[i][j];
if (j < n)
	dp[i][j+1] += dp[i][j];

 

 

직진만 가능한 경우가 있을 때에는 dp를 두개를 사용하면 됩니다.

한쪽은 오른쪽으로 이동할 때의 경우의 수만을 담고 한쪽은 아래로 이동할 때의 경우의 수만 담습니다.

vector<vector<int>> right(m, vector<int>(n, 0));
vector<vector<int>> down(m, vector<int>(n, 0));

 

else if (city_map[i][j] == 2)
{
    if (i < m - 1 && i > 0)
            down[i + 1][j] = down[i][j] % MOD;

    if (j < n - 1 && j > 0)
            right[i][j + 1] += right[i][j] % MOD;
}

 

 

정답 코드

#include <vector>
#include <iostream>

using namespace std;

int MOD = 20170805;

int solution(int m, int n, vector<vector<int>> city_map) {

    vector<vector<int>> right(m, vector<int>(n, 0));
    vector<vector<int>> down(m, vector<int>(n, 0));

    right[0][1] = 1;
    down[1][0] = 1;


    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (city_map[i][j] == 1)
                    continue;

            else if (city_map[i][j] == 2)
            {
                if (i < m - 1 && i > 0)
                    down[i + 1][j] = down[i][j] % MOD;

                if (j < n - 1 && j > 0)
                    right[i][j + 1] += right[i][j] % MOD;
            }
            else
            {
                if (i < m - 1)
                    down[i + 1][j] += (down[i][j] + right[i][j]) % MOD;

                if (j < n - 1)
                    right[i][j + 1] += (down[i][j] + right[i][j]) % MOD;
            }
        }
    }
    return (right[m - 1][n - 1] + down[m - 1][n - 1]) % MOD;
}