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

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

17070번: 파이프 옮기기 1

 

간단하게 가로일떄 세로일때 대각선일때 어떻게 파이프를 움직여나갈건지

DFS로 탐색하며 

마지막칸에 도달시 카운트를 한개씩 올려줬다.

 

 

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int n;
int cnt = 0;
 
int arr[17][17];
bool visit[17][17];
//state 가 0이면 가로상태, 1이면 세로상태, 2면 대각선상태를 나타냄
int dfs(int a, int b, int state) {
    if (a >= n || b >= n || arr[a][b] == 1) return 0;
    if (state == 2 && (arr[a][b] == 1 || arr[a - 1][b] == 1 || arr[a][b - 1] == 1)) return 0;
 
    if (a == n - 1 && b == n - 1) {
        cnt++;
        return 0;
    }    
    if (state == 0) {
        dfs(a, b + 1, 0);
        dfs(a + 1, b + 1, 2);
 
    }
    else if (state == 1) {
        dfs(a + 1, b, 1);
        dfs(a + 1, b + 1, 2);
    }
    else {
        dfs(a + 1, b, 1);
        dfs(a, b + 1, 0);
        dfs(a + 1, b + 1, 2);
    }
 
    return 0;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
    dfs(0, 1, 0);
    cout << cnt;
    return 0;
}