BOJ 17070 : 파이프 옮기기 1 [C++]

 

17070번: 파이프 옮기기 1

 

대각선으로 이동할 때 3칸을 고려해야한다는 걸 뒤늦게 알아 해결한 문제

 

BFS로 풀었는데, 대부분 DFS로 풀었고 DP로 푼 경우도 있는 것 같다.

풀고서 다시 생각해보니 DP도 좋은 풀이인 것 같다.

BFS로 풀 경우 조건을 많이 걸어 경우의 수를 좀 많이 제외시켜줘야 할 것 같다.

 

파이프의 앞 쪽 좌표와 놓인 방향을 큐에 넣어 BFS를 수행했다.

집의 벽(문제에서 1로 표현한 벽 말고)에 닿도록 가로, 세로로 놓이게 된다면 그 곳이 (N, N)이 아닌 이상

더는 움직일 수 없어 이 경우를 조건문으로 제외시켜주었다.

 

#include <iostream>
#include <queue>

int ans = 0;
int house[16][16];

void bfs(int n) {
    std::queue<std::pair<std::pair<int, int>, char>> trace;
    trace.push({{0, 1}, 'W'});

    while (!trace.empty()) {
        std::pair<int, int> cur = trace.front().first;
        char direction = trace.front().second;
        trace.pop();

        if (cur.first == n - 1 && cur.second == n - 1) {
            ans++;
            continue;
        }

        if (direction == 'W' || direction == 'L' || direction == 'D') {
            if (cur.first + 1 < n || cur.second + 1 < n) {
                if (house[cur.first + 1][cur.second] != 1 && house[cur.first][cur.second + 1] != 1 && house[cur.first + 1][cur.second + 1] != 1) {
                    trace.push({{cur.first + 1, cur.second + 1}, 'D'});
                }
            }
        }

        if (direction == 'W' || direction == 'D') {
            if (cur.first < n - 1) {
                if (cur.second + 1 < n - 1) {
                    if (house[cur.first][cur.second + 1] != 1) {
                        trace.push({{cur.first, cur.second + 1}, 'W'});
                    }
                }
            } else if (cur.first == n - 1) {
                if (cur.second + 1 < n) {
                    if (house[cur.first][cur.second + 1] != 1) {
                        trace.push({{cur.first, cur.second + 1}, 'W'});
                    }
                }
            }
        }

        if (direction == 'L' || direction == 'D') {
            if (cur.second < n - 1) {
                if (cur.first + 1 < n - 1) {
                    if (house[cur.first + 1][cur.second] != 1) {
                        trace.push({{cur.first + 1, cur.second}, 'L'});
                    }
                }
            } else if (cur.second == n - 1) {
                if (cur.first + 1 < n) {
                    if (house[cur.first + 1][cur.second] != 1) {
                        trace.push({{cur.first + 1, cur.second}, 'L'});
                    }
                }
            }
        }
    }
}

int main() {
    int n = 0;
    std::cin >> n;


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++){
            std::cin >> house[i][j];
        }
    }

    bfs(n);

    std::cout << ans << "\n";

    return 0;
}