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

 재귀를 이용한 dfs로 풀었다. 근데 풀고 나서 보니까 vertical이랑 horizontal이랑 반대로 썼다.

이 문제는 파이프를 놓거나, 추가하는 것이 아니라, 옮겨간다는 점이 중요했고,

또 무조건 도착지점이 우측 하단이라는 점도 중요했다.

 

 놓는 방향이 정해져 있고, 직전 파이프의 모양을 제외하면 현재 파이프 모양에 제약을 주는 것은 map이 1일 경우 뿐.

 

 저 조건들로 인해서 고민 할 거리가 많이 줄어든다.

 

 

#include <iostream>
const int vertical = 0;
const int horizontal = 1;
const int diagonal = 2;
// 0:가로 1:세로 2:대각
using namespace std;
int ans = 0;
int map[17][17];
int dx[] = { 0,1,1 };
int dy[] = { 1,0,1 };
int N = 0;
void recur(int row, int col, int shape) {
    if (row == N && col == N) {
        ans++;
        return;
    }
    for (int i = 0; i < 3; i++) {
        if (shape == vertical) {
            if (i == horizontal)
                continue;
        }
        if (shape == horizontal) {
            if (i == vertical)
                continue;
        }
 
        int x = row + dx[i];
        int y = col + dy[i];
        if (x > N || y > N || map[x][y] == 1) {
            continue;
        }
        if (i == 2) {
            if (x - 1 > N || y - 1 > N || map[x - 1][y] == 1 || map[x][y - 1] == 1)
                break;
            else {
                recur(x, y, i);
            }
        }
        else {
            recur(x, y, i);
        }
    }
}
int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
    recur(1, 2, 0);
    cout << ans << endl;
}