BOJ 17069 · 파이프 옮기기 2

알고리즘 분류 : 다이나믹 프로그래밍  

파이프를 옮겨서 한쪽 끝을 (N, N)으로 이동시키는 방법의 개수를 구해야 한다. BOJ 17070번 '파이프 옮기기 1'이 업그레이드된 문제이다. N의 범위가 최대 32로 증가했다. 하지만 시간제한은 0.5초로 줄어들었으므로, 백트래킹으로 구현할 수 없다. 때문에 이 문제는 DP를 이용하여 구현해야 한다. DP로 구현하면 1번 문제도 해결할 수 있다.

• 파이프의 상태는 3가지로 나눌 수 있다. 
• 1. 가로로 놓여있는 상태 (0) : 가로(0) → 가로(0) 또는 대각선(2)
• 2. 세로로 놓여있는 상태 (1) : 세로(1) → 세로(1) 또는 대각선(2)
• 3. 대각선으로 놓여있는 상태 (2) : 대각선(2) → 가로(0) 또는 세로(1) 또는 대각선(2)

• D[M][X][Y] : M번 파이프가 (X, Y)에 도착하는 방법의 수 (M은 파이프의 상태 0~2)
• D[0][X][Y] : 가로 파이프가 (X, Y)에 도착하는 방법의 수
• D[1][X][Y] : 세로 파이프가 (X, Y)에 도착하는 방법의 수
• D[2][X][Y] : 대각선 파이프가 (X, Y)에 도착하는 방법의 수
• D[0][1][2] = 1 : 가로 파이프 시작 위치 (1, 2)

---

C++ 소스코드

#include <cstdio>

int n, p[34][34];
long long d[3][34][34];

void solve() {
    d[0][1][2] = 1;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (!p[i][j+1]) d[0][i][j+1] += d[0][i][j] + d[2][i][j];
            if (!p[i+1][j]) d[1][i+1][j] += d[1][i][j] + d[2][i][j];
            if (!p[i+1][j+1] && !p[i+1][j] && !p[i][j+1]) {
                d[2][i+1][j+1] += d[0][i][j] + d[1][i][j] + d[2][i][j];
            }
        }
    }
    printf("%lld\n", d[0][n][n]+d[1][n][n]+d[2][n][n]);
}

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            scanf("%d", &p[i][j]);
        }
    }
    solve();
    return 0;
}

---

Python 3 소스코드

n = int(input())
p = [[0]*(n+1)]+[[0]+list(map(int, input().split())) for _ in range(n)]
d = [[[0]*3 for _ in range(n+1)] for _ in range(n+1)]

def solve():
    d[1][2][0] = 1
    for i in range(1, n+1):
        for j in range(1, n+1):
            if j < n and not p[i][j+1]:
                d[i][j+1][0] += d[i][j][0] + d[i][j][2]
            if i < n and not p[i+1][j]:
                d[i+1][j][1] += d[i][j][1] + d[i][j][2]
            if i < n and j < n and not (p[i+1][j] or p[i][j+1] or p[i+1][j+1]):
                d[i+1][j+1][2] += d[i][j][0] + d[i][j][1] + d[i][j][2]

solve()
print(sum(d[n][n]))

✓ 파이썬 소스코드는 D[X][Y][M] 으로 구현했다.

---

참고

• 백준 온라인 저지 : BOJ 17069
• 파이프 옮기기 1