BOJ 17070 · 파이프 옮기기 1

알고리즘 분류 : 백트래킹  

파이프를 옮겨서 한쪽 끝을 (N, N)으로 이동시키는 방법의 개수를 구해야 한다. 파이프는 2칸을 차지하지만, 파이프의 끝만 고려하면 된다.

• 파이프의 상태는 3가지로 나눌 수 있다. 
• 1. 가로로 놓여있는 상태 (0) : 가로(0) → 가로(0) 또는 대각선(2)
• 2. 세로로 놓여있는 상태 (1) : 세로(1) → 세로(1) 또는 대각선(2)
• 3. 대각선으로 놓여있는 상태 (2) : 대각선(2) → 가로(0) 또는 세로(1) 또는 대각선(2)
• 가로(0)에서 세로(1)로 곧바로 이동할 수 없고, 세로(1)에서 가로(0)로 곧바로 이동할 수 없다.

• 재귀 함수의 인자는 (X 좌표, Y 좌표, 파이프 상태) 이다.
• 현재 파이프 상태에 따라서 다음 이동의 파이프 상태를 위의 3가지 조건에 따라 구현한다.
• 또한, 다음 이동 좌표가 벽(1)인지 확인하고, 벽이라면 이동하지 않도록 한다. 빈칸(0)으로만 이동할 수 있다.
• 마지막 좌표에 도착하면 정답에 +1 카운트한다.

---

C++ 소스코드

#include <cstdio>

int n, ans;
int a[16][16];
int dx[] = {0, 1, 1}, dy[] = {1, 0, 1};

void solve(int x, int y, int z) {
    if (x == n-1 && y == n-1) {
        ans += 1;
        return;
    }
    for (int i=0; i<3; i++) {
        if (i+z == 1) continue;
        int nx = x+dx[i], ny = y+dy[i];
        if (nx >= n || ny >= n || a[nx][ny]) continue;
        if (i == 2 && (a[x][y+1] || a[x+1][y])) continue;
        solve(nx, ny, i);
    }
}

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

---

PyPy3 소스코드

dx, dy = (0, 1, 1), (1, 0, 1)
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

def solve(x, y, z):
    res = 0
    if x == n-1 and y == n-1:
        return 1
    for i in range(3):
        if i+z == 1:
            continue
        nx, ny = x+dx[i], y+dy[i]
        if nx >= n or ny >= n or a[nx][ny]:
            continue
        if i == 2 and (a[x][y+1] or a[x+1][y]):
            continue
        res += solve(nx, ny, i)
    return res

print(solve(0, 1, 0))

✓ Python 3로 제출하면 시간 초과가 나오므로, PyPy3로 제출해야 한다.

---

참고

• 백준 온라인 저지 : BOJ 17070