[백준 17069] 파이프 옮기기 2, C++

https://www.acmicpc.net/problem/17069

17069번: 파이프 옮기기 2

본 문제는 파이프 옮기기 1 문제에서 입력의 크기가 커진 문제다. dfs 탐색을 할 때, 같은 연산을 여려번 하는 경우가 발생한다. 연산량을 줄이기 위해 계산 결과를 메모이제이션 하는 DP로 문제를 풀어야 한다. 또 출력을 long long으로 하여야 한다.

#include <cstdio>
#include <cstring>
 
using namespace std;
 
int map[32][32];
 
long long d[32][32][3];
 
// now : 0 가로, 1 세로, 2 대각선
int dx[3][3] = {{0, 0, 1}, {0, 1, 1}, {0, 1, 1}};
int dy[3][3] = {{1, 0, 1}, {0, 0, 1}, {1, 0, 1}};
 
int n;
long long dfs(int x, int y, int now) {
    if (x == n-1 && y == n-1) {
        return 1;
    }
 
    // 메모이제이션
    if (d[x][y][now] != -1) return d[x][y][now];
 
    d[x][y][now] = 0;
    for (int i = 0; i < 3; i++) {
 
        // 설치할 수 없을 경우 제외하기
        if (dx[now][i] == 0 && dy[now][i] == 0) continue;
 
        int nx = x + dx[now][i];
        int ny = y + dy[now][i];
 
        if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
 
            // 가로 또는 세로로 설치할 경우
            if (i == 0 || i == 1) {
                if (map[nx][ny] == 0) d[x][y][now] += dfs(nx, ny, i);
            }
 
            // 대각선으로 설치할 경우
            else if (i == 2) {
                if (map[nx][ny] == 0 && map[nx-1][ny] == 0 && map[nx][ny-1] == 0) {
                    d[x][y][now] += dfs(nx, ny, i);
                }
            }
        }
    }
    return d[x][y][now];
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 1) map[i][j] = -1;
        }
    }
 
    memset(d, -1, sizeof(d));
    printf("%lld\n", dfs(0, 1, 0));
}