[Algorithm] 백준 17070 파이프 옮기기 - C++, DFS

17070번: 파이프 옮기기 1

#include <iostream>
#include <queue>
using namespace std;

int n;
int totalCount = 0;
int map[17][17];
// 0 - 가로, 1 - 세로, 2 - 대각선
pair<int, int> direction[] = {{0, 1}, {1, 0}, {1, 1}};

bool isOut(int y, int x){
    if(x <= 0 || y <= 0 || x > n || y > n)
        return true;
    return false;
}
bool isStuck(int y, int x){
    if(map[y][x] == 1)
        return true;
    
    return false;
}

void MakePipe(int y, int x, int dir){
    if(y == n && x == n){
        totalCount++;
        return;
    }

    for(int i = 0; i < 3; i++){
        if(i == 1 && dir == 0)  continue;
        if(i == 0 && dir == 1)  continue;

        int nextY = y + direction[i].first;
        int nextX = x + direction[i].second;

        if(isOut(nextY, nextX))     continue;
        if(isStuck(nextY, nextX))   continue;

        if(i == 2)
            if(isStuck(y+1, x) || isStuck(y, x+1))
                continue;
        MakePipe(nextY, nextX, i);
    }
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> map[i][j];
    
    MakePipe(1, 2, 0);

    cout << totalCount << '\n';
}

---

 입력값을 1부터 받아놓고 0부터 처리를 해서 계속 틀렸던 문제... 실수를 많이 줄여야 하는데 괜히 일관적이지 않은 코딩 했다가 삽질을 또 했네요.

 

 문제 풀이는 DFS로 하게 되었습니다. BFS로도 가능하지 않을까 하는데 DFS로 하면 더 간단하게 나올 수 있을 것 같아 DFS 로 풀이를 했네요. 추후 BFS도 도전을 해 보겠습니다. (DP로도 가능하지 않을까 합니다)

 각 파이프별로 다음 파이프가 올 수 있는 종류도 다르고 특히 대각선은 체크해야 할 영역이 2가지 더 있으니 이를 잘 체크해주시면 무난하게 풀 수 있을거라 생각됩니다.