파이프라인 옮기기 골드 5 (DP 말고 백트래킹)

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

문제를 읽다보면 입력 값에 N(3 ≤ N ≤ 16)란 정보를 알 수 있다. 해당 정보에 따라 무언가 백트래킹으로 해결이 가능함을 엿볼 수 있다.
그도 그럴게 파이프는 계속 오른쪽으로 옮겨지니, 경우의수가 적지 않을까 싶은 생각도 있었다.

다만 이전과 다르게 해당 문제는 파이프가 2개의 칸을 차지 하고 있는 이미지로 인해 어떻게 백트래킹을 구현할 수 있을지 고민이 된다.
=> 2개의 좌표로 인해 백트래킹이 어렵다면, 일단 하나의 좌표로 백트래킹을 구현할 수 없는지 고민해보았다.

결국 다음 좌표를 결정하는 것은 오른쪽, 아래 등 이동한 좌표의 지점이다. 그렇기 때문에 해당 좌표만 가지고 백트래킹을 구현해보면 간단하게 해결 가능하다.

그리고 백트래킹을 응용 하는 부분은 또 좌표 이동이다. 해당 정보는 2차원 배열로 관리하였다.

vector<vector<info>> d = {
{ info(0, 1, 0), info(1, 1, 2) },
{ info(0, 1, 0), info(1, 0, 1),
info(1, 1, 2) } };

다음엔 DP로 한번 풀어봐야겠다.

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

enum BD_ST { EMPTY, LAND }; 
int board[16][16];          
int n, answer = 0;          
struct info {
    int x, y, st;
    info(int _x = 0, int _y = 0, int _st = 0) : x(_x), y(_y), st(_st) {}
};

vector<vector<info>> d = {
    { info(0, 1, 0), info(1, 1, 2) },  // 가로 → 오른쪽으로 이동 또는 대각선 이동
    { info(1, 0, 1), info(1, 1, 2) },  // 세로 → 아래로 이동 또는 대각선 이동
    { info(0, 1, 0), info(1, 0, 1), info(1, 1, 2) }  // 대각선 → 세 가지 방향으로 이동
};

// 이동 가능한지 체크하는 함수
bool canMove(int x, int y, int st) {
    if (x >= n || y >= n) return false; 

    if (st == 2) { 
        if (board[x][y] == LAND || board[x-1][y] == LAND || board[x][y-1] == LAND)
            return false;
    } else if (board[x][y] == LAND) { 
        return false;
    }

    return true; // 이동 가능
}

void backtracking(info cur) {
    if (cur.x == n - 1 && cur.y == n - 1) {
        answer++;
        return;
    }

    vector<info> temp = d[cur.st];
    for (int i = 0; i < temp.size(); i++) {
        int nx = cur.x + temp[i].x;
        int ny = cur.y + temp[i].y;
        int nst = temp[i].st;

        if (canMove(nx, ny, nst)) {
            backtracking({ nx, ny, nst });
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> board[i][j];

    backtracking({ 0, 1, 0 });

    // 결과 출력
    cout << answer << endl;

    return 0;
}