17070번 파이프 옮기기 1

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

풀이

17070번 파이프 옮기기 1 문제는 $N \times N$ 크기의 격자판 위에서 $1 \times 2$ 크기의 파이프를 $(1, 1), (1, 2)$ 위치에서 $(N, N)$ 위치까지 옮기는 방법의 수를 찾는 문제입니다. 파이프는 가로, 세로, 대각선의 세 가지 방향을 가질 수 있으며, 각 방향에 따라 이동할 수 있는 규칙이 다릅니다.

문제의 핵심 규칙:

1. 가로 방향: 가로 또는 대각선으로 이동 가능.
2. 세로 방향: 세로 또는 대각선으로 이동 가능.
3. 대각선 방향: 가로, 세로, 대각선 모두 이동 가능.
4. 이동 조건: 대각선으로 이동할 때는 현재 위치를 기준으로 오른쪽, 아래, 오른쪽 아래 대각선 세 칸이 모두 비어 있어야 합니다. 가로나 세로 이동은 이동할 한 칸만 비어 있으면 됩니다.

탐색 방식 (BFS): 제공된 코드에서는 BFS(Breadth-First Search)를 사용하여 모든 가능한 경우의 수를 탐색합니다. $N$의 크기가 최대 16으로 작기 때문에 모든 경로를 탐색하는 방식(DFS)으로 해결이 가능합니다.

1. 상태 정의: 큐(Queue)에는 파이프의 끝점 좌표와 현재 방향을 저장합니다.
   • orientation: 0(가로), 1(세로), 2(대각선)

2. 이동 가능 여부 체크 (canMovable): 각 방향별로 격자 범위를 벗어나지 않는지, 벽(1)에 부딪히지 않는지 확인합니다. 특히 대각선 이동 시에는 3칸의 빈 공간을 체크해야 하는 점이 중요합니다.

3. 결과 도출: 파이프의 끝점이 $(N-1, N-1)$에 도달할 때마다 결과값(res)을 1씩 증가시킵니다.

시간 복잡도: 이 문제의 상태 공간은 $(N \times N)$ 위치와 3가지 방향의 조합인 $O(3^{N^2})$입니다. 하지만 BFS의 가지치기로 인해 대략 천만번 안에 계산이 됩니다.

코드

17070.cpp

#include <bits/stdc++.h>
using namespace std;
constexpr array<array<int, 3>, 3> moves = {{
    {0, 2, -1}, 
    {1, 2, -1}, 
    {0, 1, 2}
}};
constexpr array<pair<int, int>, 3> coord = {{
    {0, 1},
    {1, 0},
    {1, 1}
}};
const bool canMovable(const auto& board, const pair<int, int> &coord, const int ori){
    const int N = board.size();
    switch(ori){
        case 0:
            if(coord.second + 1 >= N || board[coord.first][coord.second + 1] != 0)
                return false;
        break;
        case 1:
            if(coord.first + 1 >= N || board[coord.first + 1][coord.second] != 0)
                return false;
        break;
        case 2:
            if(coord.first + 1 >= N || coord.second + 1 >= N)
                return false;
            if(board[coord.first + 1][coord.second] != 0)
                return false;
            if(board[coord.first][coord.second + 1] != 0)
                return false;
            if(board[coord.first + 1][coord.second + 1] != 0)
                return false;
        break;
    }
    return true;
}
int BFS(const auto& board){
    const int N = board.size();
    queue<pair<pair<int, int>, int>> q;
    q.push({{0, 1}, 0});
    int res = 0;
    while(!q.empty()){
        auto currOrientation = q.front().second;
        auto currCoord = q.front().first;
        q.pop();
        for(int i = 0; i < 3; i++){
            if(moves[currOrientation][i] == -1)
                continue;
            if(!canMovable(board, currCoord, moves[currOrientation][i]))
                continue;
            auto nextOrientation = moves[currOrientation][i];
            pair<int, int> nextCoord = { currCoord.first + coord[nextOrientation].first, currCoord.second + coord[nextOrientation].second };
            if(nextCoord.first == N - 1 && nextCoord.second == N - 1){
                res++;
                continue;
            }
            q.push({nextCoord, nextOrientation});
        }
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    auto board = vector(N, vector(N, -1));
    for(auto& row: board){
        for(auto& e: row){
            cin >> e;
        }
    }
    // Initialize
    board[0][0] = 1;
    board[0][1] = 1;
    cout << BFS(board) << "\n";
    return 0;
}

Standard Input (stdin): 3 0 0 0 0 0 0 0 0 0

⏳ Running... C++