문제

세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다.

따라서, 아래 그림과 같이 생겼다.

도로 이미지

세준이는 집에서 학교로 가는 길의 경우의 수가 총 몇 개가 있는지 궁금해지기 시작했다.

세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다.

(0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은 자연수이다. 셋째 줄부터 K개 줄에는 공사중인 도로의 정보가 a b c d와 같이 주어진다. a와 c는 0보다 크거나 같고, N보다 작거나 같은 자연수이고, b와 d는 0보다 크거나 같고, M보다 작거나 같은 자연수이다. 그리고, (a, b)와 (c, d)의 거리는 항상 1이다.

출력

첫째 줄에 (0, 0)에서 (N, M)까지 가는 경우의 수를 출력한다. 이 값은 0보다 크거나 같고, \(2^{63} - 1\)보다 작거나 같은 자연수이다.

접근 과정

(N, M)까지 가는 경로의 갯수를 세는 문제이다. 재귀호출을 통해 경로를 탐색하되 각 지점에서 (N, M) 까지 갈 수 있는 경우의 수를 기록하여 중복되는 탐색 경로가 생기지 않도록 구현하면 될 것 같았다. (Dynamic Programming)
여기서 고려해야 할 부분은 공사중인 경로로는 이동할 수 없다는 것이다. 이를 어떻게 저장하고 탐색중 확인할지 고민하였고 이동할 수 없는 방향에 대해 비트 플래그로 표시를 하는 것으로 정했는데 속도도 빠르고 코드도 깔끔해질 것 같았기 때문이다.
N과 M이 커질수록 경로의 수가 많아지기 떄문에 오버플로우를 방지하기 위해 결과 값의 자료형을 long long으로 선언해주어야 한다. (메모이제이션 초기값이 -1이 아니라면 unsigned long을 사용해 메모리 효율을 높일 수도 있겠다.)
다 풀어놓고 함수 내 ret 변수를 int형으로 선언하는 바람에 왜 틀리는지 몰라 시간을 많이 낭비했다. 항상 오버플로우를 주의하자 ㅠㅠ

소스 코드

#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;

#define UP 1
#define RIGHT 2

int N, M, K;
int blocks[101][101];
long long path[101][101];

long long moveFrom(int x, int y) {
    if (x == N && y == M) {
        return 1;
    }

    if (path[y][x] != -1) {
        return path[y][x];
    }

    long long ret = 0;
    if (x != N && (blocks[y][x] & RIGHT) == 0) {
        assert(x + 1 <= N);
        ret += moveFrom(x + 1, y);
    }

    if (y != M && (blocks[y][x] & UP) == 0) {
        assert(y + 1 <= M);
        ret += moveFrom(x, y + 1);
    }
    path[y][x] = ret;
    return ret;
}

int main(void) {
    memset(path, -1, sizeof(path));
    
    cin >> N >> M;
    cin >> K;

    for (int i = 0; i < K; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        if (x1 == x2) {
            blocks[y1 < y2 ? y1 : y2][x1] |= UP;
        } else {
            assert(y1 == y2);
            blocks[y1][x1 < x2 ? x1 : x2] |= RIGHT;
        }        
    }

    cout << moveFrom(0, 0) << endl;
    return 0;
}