도로의 개수 1577

문제

접근 방법

N, M 지점까지 경로의 경우의 수는 밑과 왼쪽의 경우를 합하면 된다.
하지만 이 문제에서 한 가지 문제가 존재한다.
공사 중인 도로가 존재한다는 것이다.
공사 중인 도로를 체크하여 그 값은 가져오지 말아야 한다.

4차원 배열로 하면은 큰 값이 나오기에 16MB 제한을 넘을 것으로 예상된다.
그렇다면 다른 수단을 써야 하는데 결국 다른 좌표로 가는 길은 2개라는 점을 생각하면 3차원 배열로 해결할 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<ll>> dp(N + 1, vector<ll>(M + 1));
    vector<vector<vector<bool>>> block(N + 1, vector<vector<bool>>(M + 1, vector<bool>(2)));
    while (K--)
    {
        int i, j, k, l;
        cin >> i >> j >> k >> l;
        if (i > k) // 위쪽으로 가는 길
            block[k][l][0] = true;
        else if (j > l) // 오른쪽으로 가는 길
            block[k][l][1] = true;
        else if (k > i) // 위쪽으로 가는 길
            block[i][j][0] = true;
        else // 오른쪽으로 가는 길
            block[i][j][1] = true;
    }
    dp[0][0] = 1;
    for (int i = 1; i <= N; ++i)
    {
        if (block[i - 1][0][0])
            break;
        dp[i][0] = 1;
    }
    for (int i = 1; i <= M; ++i)
    {
        if (block[0][i - 1][1])
            break;
        dp[0][i] = 1;
    }
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= M; ++j)
        {
            if (!block[i - 1][j][0])
            {
                dp[i][j] += dp[i - 1][j];
            }
            if (!block[i][j - 1][1])
            {
                dp[i][j] += dp[i][j - 1];
            }
        }
    }
    cout << dp[N][M];
    return 0;
}

풀이

처음에는 0, 0 또는 N, M만 안 겹치면 둘 중 아무 좌표를 막으면 된다고 생각했다. 하지만 순서에 따라 값이 달라질 수 있기에 틀린 방법임을 깨달았다.

그래서 나온 것이 2개의 좌표와 방향으로 해결하는 방법이었다.
처음 제출했을 때 틀렸는데 다시 확인해 보니 사소하게 변수를 잘못 적어서 틀렸었다.

문제를 푸는 데 있어서 사소한 부분이 생각보다 크게 작용하니 조심해야 하는데 그게 쉽지 않은 것 같다.