[BOJ] 파이프옮기기1

[문제]

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

17070번: 파이프 옮기기 1

[풀이]

 

1) dfs 로 해결함.

 

2) 가로 방향 파이프는 갈 수 있는 방향이 가로와 대각선

세로 방향 파이프는 갈 수 있는 방향이 세로와 대각선

대각선은 세로, 가로, 대각선을 모두 갈 수 있다.

 

3) (1,2)에서부터 가로, 세로, 대각선 방햐으로 뻗어나갈 수 있다. 단, (1,3)이 벽이라면 어떤 방법으로도 나아갈 수 없기 때문에 가지치기 한다.

 

4) dfs(세로, 가로, 방향) 으로 파라미터를 줬고, 방향에 따라서 갈 수 있는 방향으로 재귀호출한다. 

• dir == 0 ( 가로) 일 경우 오른쪽 방향이 벽인지 아닌지 확인한다. 
  벽이 아니라면 대각선, 세로 방향이 벽인지 아닌지 확인하고 벽이 아니라면 모든 방향으로 탐색을 진행한다. 
  만약, 벽이라면 오른쪽 방향으로 계속 나아간다. 
• dir == 1 도 같은 방식
• dir == 2  (대각선)은 약간의 조건이 더 필요하다. 
  먼저, 오른쪽 방향이 벽이 아니라면 대각선, 세로 방향을 살펴보고 모든 방향으로 탐색을 진행한다. 
  그 후에 세로 방향이 벽이 아니라면 가로, 세로로 탐색을 진행한다. 
  세로방향이 벽이라면 가로 방향으로만 진행한다. 
  
  왼쪽 방향이 벽이 아니라면 세로 방향으로 계속 진행한다. 

---

#include <iostream>
using namespace std;
 
int n, map[17][17];
 
int dfs(int x, int y, int dir) {
    if (x == n && y == n) return 1;
 
    if (x > n || y > n) return 0;
 
    if (dir == 0) {
        //가로 
        if (!map[x][y+1]) {
            //오른쪽방향이 벽이 아니라면 
            if (!map[x+1][y+1] && !map[x+1][y]) 
                return dfs(x+1, y+1, 2) + dfs(x,y+1, 0); //갈 수 있는 모든 방향을 살펴봄 
            else 
                return dfs(x, y+1, 0); //현재 방향으로 계속 나아간다. 
        }
        return 0;
    }
    else if (dir == 1) {
        //세로 
        if (!map[x+1][y]) {
            if (!map[x+1][y+1] && !map[x][y+1]) {
                return dfs(x+1, y+1, 2) + dfs(x+1, y, 1);
            }
            else
                return dfs(x+1, y, 1);
        }
        return 0;
    }
    else {
        //대각선 -> 모든 방향으로 나아갈 수 있기 때문에 조건문이 더 필요함 
        if (!map[x][y+1]) {
            //일단 오른쪽이 비었을 때 
            if (!map[x+1][y+1] && !map[x+1][y]) {
                return dfs(x+1, y+1, 2) + dfs(x, y+1, 0) + dfs(x+1, y, 1);
            }
            if (!map[x+1][y]) {
                return dfs(x, y+1, 0) + dfs(x+1, y, 1);
            }
            else
            {
                return dfs(x, y+1, 0);
            }
        }
        if(!map[x+1][y]) {
            return dfs(x+1, y, 1);
        }
        return 0;
    }
    return 0;
}
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }
 
    if (map[1][3] == 1) cout << 0 << '\n';
    else {
        cout << dfs(1, 2, 0) << '\n'; //세로 가로 방향 
    }
    return 0;
}