[백준 17070] 파이프 옮기기 1, C++

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

17070번: 파이프 옮기기 1

본 문제는 가로, 세로, 대각선으로 파이프를 설치하여 n-1, m-1에 도착하는 경우의 수를 출력하는 문제다. 1은 벽이고 파이프를 설치하는 방법은 다음과 같다.

1. 이전 파이프가 가로일 경우 : 가로, 대각선
2. 이전 파이프가 세로일 경우 : 세로, 대각선
3. 이전 파이프가 대각선일 경우 : 가로, 세로, 대각선

문제에서 벽을 1로 하였지만 소스코드에서는 -1로 변경하였다. dfs 탐색을 하면서 n-1, m-1에 도착하였을 때 1씩 증가하면 된다.

#include <cstdio>
 
using namespace std;
 
int map[20][20];
 
// 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;
int ans = 0;
void dfs(int x, int y, int now) {
    if (x == n-1 && y == n-1) {
        ans += 1;
        return;
    }
    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) dfs(nx, ny, i);
            }
 
            // 대각선으로 설치할 경우
            else if (i == 2) {
                if (map[nx][ny] == 0 && map[nx-1][ny] == 0 && map[nx][ny-1] == 0) {
                    dfs(nx, ny, i);
                }
            }
        }
    }
}
 
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;
        }
    }
 
    dfs(0, 1, 0);
    printf("%d\n", ans);
}