백준 17070문제(DFS 이용)

#include <bits/stdc++.h>
using namespace std;

int N;
int arr[17][17];

//1 : 가로 ,2 : 세로 , 3 : 대각선

bool chk(int x, int y){
    if(x<=N && y<=N && arr[x][y] != 1) return true;
    return false;
}

int go(int x, int y, int status){
    if(x == N && y == N) return 1;

    int ret = 0;
    bool move[3] = {chk(x+1,y), chk(x, y+1), chk(x+1, y+1)};

    if(status == 1){
        if(move[1])
            ret += go(x,y+1,1);
        if(move[1] && move[0] && move[2])
            ret += go(x+1, y+1,3);
    }
    else if(status == 2){
        if(move[0])
            ret += go(x+1,y,2);
        if(move[0] && move[2]  && move[1])
            ret += go(x+1, y+1,3);
        }
    else{
        if(move[1])
            ret+= go(x, y+1,1);
        if(move[0])
            ret+= go(x+1, y,2);
        if(move[0] && move[1] && move[2])
            ret+= go(x+1, y+1,3);
    }

    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    
    cin >> N ;

    for(int i=1 ; i<=N ; i++)
        for(int j=1 ; j<=N ; j++)
            cin >> arr[i][j];

    cout << go(1,2,1);

    return 0;
}

백준 파이프 옮기기1문제 DFS풀이입니다.