[백준] 17070번 파이프 옮기기1 C++ 코드

코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, a[18][18], dp[18][18][4]; // 상태값은 3개: x좌표, y좌표, 방향
// 1은 가로, 2는 세로, 3은 대각선
int go(int x, int y, int dir) {
    if(x >= n || y >= n || (a[x][y] == 1)) return 0; // 벽인지 아닌지 확인
    // 대각선으로 움직이는 경우는 추가 확인 필요
    if(dir == 3 && (a[x - 1][y] == 1 || a[x][y - 1] == 1)) return 0; 
    if((x == n - 1) && (y == n - 1)) return 1; // 목표지점 도달
    if(dp[x][y][dir] != -1) return dp[x][y][dir]; // 메모이제이션
    int r = 0;
    int dr = 0;
    int d = 0;
    if(dir == 1) {
    	// 가로로 온 경우는 가로 또는 대각선만
        r = go(x, y + 1, 1);
        dr = go(x + 1, y + 1, 3);
    }
    if(dir == 2) {
	    // 세로로 온 경우는 세로 또는 대각선만
        d = go(x + 1, y, 2);
        dr = go(x + 1, y + 1, 3);
    }
    if(dir == 3) {
    	// 대각선으로 온 경우는 모든 경우 가능
        r = go(x, y + 1, 1);
        d = go(x + 1, y, 2);
        dr = go(x + 1, y + 1, 3);
    }
    dp[x][y][dir] = (d + r + dr); // 경우의 수를 합해줌
    return dp[x][y][dir];
}

// 방법의 수는 가로, 세로, 대각선
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    cout << go(0,1,1) << '\n'; // 0,1부터 시작, 가로방향
    return 0;
}

풀이

파이프는 가로, 세로, 대각선 3가지 방향으로 놓을 수 있다. 가로로 놓는 경우는 가로, 대각선으로, 세로는 세로 또는 대각선, 대각선은 모든 방향으로 배치가 가능하다. 그리고 대각선으로 가는 경우, 벽이 있는지 추가로 확인해야한다.

 

이렇게 케이스를 분류한 뒤 점화식을 세운다. 문제의 조건에 유향 비순환 그래프(DAG)임을 알 수 있었고, 이전의 상태를 이용할 수 있기 때문에 dp를 풀이 방법으로 생각했다. 상태는 x좌표, y좌표, 방향 3가지가 필요하므로 dp테이블을 3차원 배열로 구성했다. 그 후 top-down 방식으로 문제를 해결했다.