백준 / 17070 / 파이프 옮기기 1 / C++

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

#include <bits/stdc++.h>

using namespace std;

// 1차원 인덱스 : 초기상태 가로, 세로, 대각선(0,1,2)
// 2차원 인덱스 : 다음상태에서 체크해야 할 모양
// 3차원 인덱스 : 다음상태에서 실제로 체크해야 할 좌표값
vector<vector<vector<int>>> dx = {{{0}, {0, 1, 1}}, {{1}, {0, 1, 1}}, {{0}, {1}, {0, 1, 1}}};
vector<vector<vector<int>>> dy = {{{1}, {1, 0, 1}}, {{0}, {1, 0, 1}}, {{1}, {0}, {1, 0, 1}}};
vector<vector<int>> arr;
int n;
int ans = 0;

void dfs(int x, int y, int curstate)
{
    if (x == n - 1 && y == n - 1)
    {
        ans++;
        return;
    }
    if (curstate == 0)
    {
        for (int i = 0; i < dx[curstate].size(); i++)
        {
            int size = dx[curstate][i].size();
            bool flag = true;
            for (int j = 0; j < size; j++)
            {
                int nx = x + dx[curstate][i][j];
                int ny = y + dy[curstate][i][j];
                if (nx >= n || ny >= n || nx < 0 || ny < 0)
                {
                    flag = false;
                    break;
                }
                if (arr[nx][ny] == 1)
                {
                    flag = false;
                    break;
                }
            }
            if (!flag)
            {
                continue;
            }
            else
            {
                if (i == 0)
                {
                    dfs(x, y + 1, 0);
                }
                else if (i == 1)
                {
                    dfs(x + 1, y + 1, 2);
                }
            }
        }
    }
    else if (curstate == 1)
    {
        for (int i = 0; i < dx[curstate].size(); i++)
        {
            int size = dx[curstate][i].size();
            bool flag = true;
            for (int j = 0; j < size; j++)
            {
                int nx = x + dx[curstate][i][j];
                int ny = y + dy[curstate][i][j];
                if (nx >= n || ny >= n || nx < 0 || ny < 0)
                {
                    flag = false;
                    break;
                }
                if (arr[nx][ny] == 1)
                {
                    flag = false;
                    break;
                }
            }
            if (!flag)
            {
                continue;
            }
            else
            {
                if (i == 0)
                {
                    dfs(x + 1, y, 1);
                }
                else if (i == 1)
                {
                    dfs(x + 1, y + 1, 2);
                }
            }
        }
    }
    else if (curstate == 2)
    {
        for (int i = 0; i < dx[curstate].size(); i++)
        {
            int size = dx[curstate][i].size();
            bool flag = true;
            for (int j = 0; j < size; j++)
            {
                int nx = x + dx[curstate][i][j];
                int ny = y + dy[curstate][i][j];
                if (nx >= n || ny >= n || nx < 0 || ny < 0)
                {
                    flag = false;
                    break;
                }
                if (arr[nx][ny] == 1)
                {
                    flag = false;
                    break;
                }
            }
            if (!flag)
            {
                continue;
            }
            else
            {
                if (i == 0)
                {
                    dfs(x, y + 1, 0);
                }
                else if (i == 1)
                {
                    dfs(x + 1, y, 1);
                }
                else if (i == 2)
                {
                    dfs(x + 1, y + 1, 2);
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    cin >> n;
    arr.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
        }
    }
    dfs(0, 1, 0);
    cout << ans;
}

발상은 어렵지 않았는데 구현하는데 의외로 애를 먹은 문제...

현재 상태와 현재 상태에 따라 체크해야 하는 다음 구간의 좌표를 체크하고, 옮기는 게 가능하다면 다음 파이프 끝부분 좌표와 다음 상태를 넘겨주는 DFS를 통해 풀려고 했으나 구현하다 보니 엄청난 하드코딩이 된 것 같다.

AC를 받았지만 3 ≤ N ≤ 16이라는 작은 입력 크기와 방법의 수가 항상 1,000,000보다 작거나 같다는 널널한 조건이 붙어서 성공한 것 같아 최적화에 있어서 여러모로 아쉬움이 많이 남은 문제.