BOJ(17070) - 파이프 옮기기 1 (C++)

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

---

문제 설명

NxN 크기의 방이 1x1크기의 정사각형 칸으로 나누어져 있습니다.
오늘은 집 수리를 위해 파이프를 옮기려고 합니다. 파이프는 아래와 같은 형태이고 2개의 연속된 칸을 차지하는 크기입니다.

파이프는 가로, 세로, 대각선 방향으로 회전시킬 수 있습니다.

파이프는 매우 무겁기 때문에 파이프를 밀면서 이동시키려고 합니다. 이 때 파이프를 밀면서 회전시킬 수 있습니다.
파이프는 →, ↘, ↓ 방향으로만 밀 수 있습니다. 이때, 파이프가 가로로 놓여져 있는 경우 →, ↘ 방향으로만, 세로로 놓여져있는 경우 ↘, ↓ 방향만, 대각선 방향인 경우 3방향으로 이동시킬 수 있습니다.

파이프를 밀거나 혹은 밀면서 회전시킬 때 색이 칠해져 있는 칸은 벽이 아니어야 합니다.

가장 처음 파이프가 (1, 1), (1, 2)에 있을 때 파이프의 한 쪽 끝을 (N, N)으로 이동시키는 방법의 개수를 구하시오.

제한조건

N <= 16

---

아이디어

N은 16이여서 완전탐색이 가능합니다. 이때 0, 1, 2 를 각각 오른쪽, 대각선, 아래쪽 방향으로 잡아 구현했습니다.
이떄 대각선인 경우 회전하며 주변에 벽이 없어야 하기 때문에 조건을 추가했습니다.

---

코드

#include <bits/stdc++.h>

#define X first
#define Y second

using namespace std;

int dx[] = {0, 1, 1};
int dy[] = {1, 1, 0};

int n;
vector<vector<int>> board(16, vector<int>(16));
pair<int, pair<int, int>> rootP = {0, {0, 1}};
int res = 0;

void solution(pair<int, pair<int, int>> pipe)
{
    if(pipe.second.X == n-1 && pipe.second.Y == n-1)
    {
        res++;
        return;
    }

    switch (pipe.first)
    {
        case 0: // vertical
            for(int i = 0; i < 2; i++)
            {
                int nx = pipe.second.X + dx[i];
                int ny = pipe.second.Y + dy[i];
                if(nx >= n || ny >= n)
                    continue;
                if(board[nx][ny] != 0)
                    continue;
                if(i == 1 && (board[nx-1][ny] != 0 || board[nx][ny-1] != 0))
                    continue;
                solution({i, {nx, ny}});
            }
            break;
        case 1: // diagonal
            for(int i = 0; i < 3; i++)
            {
                int nx = pipe.second.X + dx[i];
                int ny = pipe.second.Y + dy[i];
                if(nx >= n || ny >= n)
                    continue;
                if(board[nx][ny] != 0)
                    continue;
                if(i == 1 && (board[nx-1][ny] != 0 || board[nx][ny-1] != 0))
                    continue;
                solution({i, {nx, ny}});
            }
            break;
        case 2: //horizontal
            for(int i = 1; i < 3; i++)
            {
                int nx = pipe.second.X + dx[i];
                int ny = pipe.second.Y + dy[i];
                if(nx >= n || ny >= n)
                    continue;
                if(board[nx][ny] != 0)
                    continue;
                if(i == 1 && (board[nx-1][ny] != 0 || board[nx][ny-1] != 0))
                    continue;
                solution({i, {nx, ny}});
            }
            break;
    }
}

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

    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> board[i][j];
        }
    }
    solution(rootP);
    cout << res;
}

메모리: 2020 KB, 시간: 140 ms

---

풀이 후 다른 내용을 보니 DP가 더 접근성이 쉬운 문제였습니다..