[백준/BFS&DFS/C++] 17070번 파이프 옮기기1 * (삼성 코딩테스트)

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

17070번: 파이프 옮기기 1

#include <bits/stdc++.h>

using namespace std;


int N;
int MAP[17][17];
int dx[] = {0, 1, 1};
int dy[] = {1, 0, 1};
int result = 0;

bool chk(int r, int c){
    if(r<1 || r>N ||  c<1 || c>N || MAP[r][c]==1) return false;
    else return true;
}

void dfs(int r, int c, int dir){

    if(r==N && c==N){
        result++;
        return;
    }

    for(int i=0; i<3; i++){
        // 가로>세로, 세로>가로 제외
        if((dir==0 && i==1) || (dir==1 && i==0)) continue;

        int nr = r + dx[i];
        int nc = c + dy[i];
        if(!chk(nr, nc)) continue; // 범위 벗어나거나 벽인경우
        if(i==2 && (MAP[r+1][c]==1 || MAP[r][c+1]==1)) continue; // 대각선인데 나머지 칸이 벽인경우
        dfs(nr, nc, i);
    }
}

void input(){
    cin >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> MAP[i][j];
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    dfs(1,2,0);
    cout << result;

    return 0;
}