[ 프로그래머스 보행자 천국 (Lv3) ] (C++)

프로그래머스의 보행자 천국 (Lv3) 문제이다.

[ 문제풀이 ]

(0, 0)에서 부터 (m - 1, n - 1)까지 갈 수 있는 가능한 경로의 수를 구해야 하는 문제이다.

먼저, 움직일 수 있는 방향을 살펴보면, 아래쪽으로 움직이거나, 오른쪽으로 움직일 수 만 있다. 즉, 움직일 수 있는 방향은 2가지만 존재한다는 것이다.

그럼, 어떤 좌표에서 (x , y)로 가는 경우를 생각볼건데, 여기서 추가적으로 "어떤 방향으로 나아갈 것인지?" 까지 생각을 해보자. 우리에게 주어진 나아갈 수 있는 방향이 2가지가 있으니까 그 방향 또한 생각하면서 진행해보자.

# Case1 - 1: (x , y) = 0 이고, (x , y) 에서 오른쪽 방향으로 진행하려는 상황.

(x , y)가 0이기 떄문에, 어느 방향에서 들어오던 상관없이 무조건 오른쪽 방향으로 진행할 수가 있다.

즉 ! (x - 1, y)에서 아래쪽으로 내려오는 경우도 차를 방향을 틀어서 오른쪽으로 나아갈 수 있고, (x , y - 1)에서 오른쪽으로 들어오는 경우도 그대로 직진해서 오른쪽으로 나아갈 수 있다.

# Case1 - 2 : (x , y) = 0 이고 , (x , y)에서 아래쪽으로 진행하려는 상황

마찬가지이다. 그 어떤 좌표에서 어떤 방향으로 들어오던 상관없이 진행할 수가 있다.

즉 ! (x - 1 , y)에서 아래쪽으로 내려오는 경우도 그대로 쭉 아래쪽으로 나아갈 수 있고, (x , y - 1)에서 오른쪽으로 들어오는 경우도 차를 꺾어서 아래쪽으로 나아갈 수 있다.

# Case2 : (x , y) = 1.

(x , y)가 통행이 금지된 구역이기 때문에, 어떤 방향으로 진행한다는 것 자체가 모순이 되는 상황이다.

# Case3 - 1 : (x , y) = 2 이고, (x , y) 에서 오른쪽 방향으로 진행하려는 상황.

(x , y)가 2이기 떄문에, 방향을 꺾을 수가 없다. 따라서, (x , y)에서 오른쪽 방향으로 진행하기 위해서는 반드시 (x , y - 1)에서 오른쪽으로 들어오는 경우만 (x , y)에서 오른쪽 방향으로 진행할 수가 있다.

# Case3 - 2 : (x , y) = 2 이고, (x , y)에서 아래쪽 방향으로 진행하려는 상황.

마찬가지로 방향을 꺾을 수가 없기 때문에, (x , y)에서 아래쪽으로 진행하기 위해서는 반드시 (x - 1, y)에서 아래쪽으로 들어오는 경우만 (x , y)에서 아래쪽 방향으로 진행할 수가 있다.

위의 내용을 구현하는 것에 대해서 알아보자.

본인은 3차원 배열 하나를 이용해서 문제를 해결해 주었다. 간단하게 수식으로 나타내서 F[A][B][C] = D 라고 표현할 수 있는데, F[A][B][C] = D의 의미는 "(A , B)에서 C방향으로 진행하려고 할 때, 그 경우의 수는 D가지가 있습니다." 를 의미한다.

즉 ! C는 방향을 나타내는 인덱스이기 때문에 2칸만 설정해 주었다. 왜 ? 오른쪽으로 진행하려는 경우, 아래쪽으로 진행하려는 경우 2가지 경우만 있으면 되기 때문이다. 본인은 아래쪽으로 진행하는 것을 '0'으로, 오른쪽으로 진행하는 것을 '1'로 표현하겠다. 이제 이를 이용해서 위의 Case들을 수식으로 나타내보자.

# Case1 - 1 : F[x][y][0] = F[x - 1][y][0] + F[x][y - 1][1]

위의 수식을 풀어서 설명해보면, (x , y)가 0일 때, (x , y)에서 아래쪽으로 진행하려고 할 때, 그 경우의 수는, (x - 1 , y)에서 아래쪽으로 들어오는 경우 + (x , y - 1)에서 오른쪽으로 들어오는 경우 입니다. 이다.

# Case1 - 2 : F[x][y][1] = F[x - 1][y][0] + F[x][y - 1][1]

# Case2 : F[x][y][0] = F[x][y][1] = 0

# Case3 - 1 : F[x][y][0] = F[x - 1][y][0]

# Case3 - 2 : F[x][y][1] = F[x][y - 1][1]

이렇게 표현할 수가 있다.

그런데 ! 이대로 코드를 구현하면 한가지 문제가 발생하게 된다.

왜냐하면 문제에서 주어진 맵은, (0, 0)에서 (m - 1, n - 1)의 범위를 가지고 있기 때문에, 가장 윗줄 혹은 가장 왼쪽줄의 경우에는 'x - 1, y - 1' 과 같이 음수 인덱스에 접근하려는 문제가 발생할 수 있다.

그래서 이 부분을 따로 처리해줘도 상관은 없다. 그런데 본인은 그냥 (1 , 1)부터 움직이는 것으로 계산을 했다.

조금 더 구체적으로 이야기해보면, 실질적인 비교는 (0 , 0)부터 한다. 왜냐하면 맵의 좌표가 (0 , 0)부터 있기 때문이다.

그런데 ! 값의 갱신은 (1 , 1)부터 한다는 것이다.

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (city_map[i - 1][j - 1] == 0)
            {
                DP[i][j][0] = (DP[i][j][0] + DP[i - 1][j][0] + DP[i][j - 1][1]) % MOD;
                DP[i][j][1] = (DP[i][j][1] + DP[i - 1][j][0] + DP[i][j - 1][1]) % MOD;
            }
            else if (city_map[i - 1][j - 1] == 1) DP[i][j][0] = DP[i][j][1] = 0;
            else
            {
                DP[i][j][0] = DP[i - 1][j][0] % MOD;
                DP[i][j][1] = DP[i][j - 1][1] % MOD;
            }
        }
    }

위의 코드에서 DP[][][] 배열이 위에서 언급한 수식인 F[][][] 를 의미한다.

line1 , 3)에서는 1 ~ N까지, 1 ~ M까지 탐색을 하는 것을 확인할 수 있다. 그런데 line 5 , 10 , 11)에서는 (i - 1, j - 1)의 좌표를 확인하는 것을 알 수 있다. 그리고 line 7 , 8 , 10 , 13 , 14)에서 DP[][][]배열에 저장하는 것은 (i , j)의 값을 저장하는 것을 확인할 수가 있다. 이렇게 구현한 이유는, 아까도 말했듯이, 주어진 맵과 동일하게 (0 , 0)부터 계산을 하게 되면 음수 인덱스값에 접근하려는 문제가 발생하게 되고, 이를 따로 처리해주어야 하는데, 위와 같이 구현하면 따로 처리해주지 않아도 한번에 처리를 할 수 있기 때문이다. 왜냐하면 (1 , 1) ~ (M , N)까지의 값을 저장한다고 했을 때, i - 1 혹은 j -1의 값이 0을 가르키는 부분이 나오게 되더라도, 이 부분은 값의 갱신이 없었기 때문에 초기값인 0을 가지고 있을 것이기 때문이다.

그래서 위와 같이, "실질적인 비교는 (i - 1, j - 1)로 비교, 값의 저장은 (i , j)에 저장" 하는 식으로 구현을 하였다.

그리고 또 한가지 차이점이 line 7 , 8)을 보게되면 위에서 설명할 때에는 F[x][y][0] = F[x - 1][y][0] + F[x][y - 1][1] 이라고 하였는데, 그 앞에 F[x][y][0] 가 추가적으로 붙은 형태로 존재하는 것을 확인할 수 있다.

이는, 초기 값인 DP[1][1][0], DP[1][1][1]의 값을 '1'로 본인이 따로 설정해 주었는데, 위와 같이 구현하지 않고, 앞에서 설명한 수식처럼 식을 쓰게 되면, (1 , 1)부터 값의 갱신이 일어나지 않아서 모든 좌표에 대한 값의 갱신이 이루어질 수 없어서 위와 같이 구현해 주었다.

[ 소스코드 ]

#include <vector>
#include <cstring>
 
using namespace std;
 
int N, M;
int DP[510][510][2];
int MOD = 20170805;
 
int solution(int m, int n, vector<vector<int>> city_map) 
{
    N = m;
    M = n;
    memset(DP, 0, sizeof(DP));
    DP[1][1][0] = DP[1][1][1] = 1;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (city_map[i - 1][j - 1] == 0)
            {
                DP[i][j][0] = (DP[i][j][0] + DP[i - 1][j][0] + DP[i][j - 1][1]) % MOD;
                DP[i][j][1] = (DP[i][j][1] + DP[i - 1][j][0] + DP[i][j - 1][1]) % MOD;
            }
            else if (city_map[i - 1][j - 1] == 1) DP[i][j][0] = DP[i][j][1] = 0;
            else
            {
                DP[i][j][0] = DP[i - 1][j][0] % MOD;
                DP[i][j][1] = DP[i][j - 1][1] % MOD;
            }
        }
    }
    return DP[N][M][0] % MOD;
}