[C++] BOJ 1941번: 소문난 칠공주

문제 링크

문제 풀이

정답율이 높아 쉬울 거라 생각하고 접근하였는데, 상상 이상으로 어려운 문제였다. 백트래킹을 이용하여 풀었는데 처음에는 y좌표와 x좌표를 나누어 백트래킹하였고 이로 인해 문제를 해결하지 못하였다. p라는 변수로 좌표(point)를 하나로 합쳐 y좌표는 p / 5, x좌표는 p % 5로 하여 문제를 풀었고 결과적으로 해결되었다.

코드

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

char map[10][10];
bool checked[10][10];
bool checkedConnection[10][10];

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

queue<pair<int, int>> q;

bool checkConnected()
{

    for (int y = 0; y < 5; y++)
        for (int x = 0; x < 5; x++)
            checkedConnection[y][x] = false;

    for (int y = 0; y < 5; y++)
    {
        for (int x = 0; x < 5; x++)
        {
            if (checked[y][x])
            {
                int cnt = 0;
                int dasomCnt = 0;
                q.push({y, x});
                checkedConnection[y][x] = true;
                if (map[y][x] == 'S')
                    dasomCnt++;
                cnt++;
                while (!q.empty())
                {
                    pair<int, int> cpos = q.front();
                    q.pop();
                    int cx = cpos.second;
                    int cy = cpos.first;

                    for (int i = 0; i < 4; i++)
                    {
                        int nx = cx + dx[i];
                        int ny = cy + dy[i];
                        if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5)
                            continue;
                        if (!checked[ny][nx] || checkedConnection[ny][nx])
                            continue;
                        q.push({ny, nx});
                        checkedConnection[ny][nx] = true;
                        cnt++;
                        if (map[ny][nx] == 'S')
                            dasomCnt++;
                    }
                }

                if (cnt == 7 && dasomCnt >= 4)
                {
                    return true;
                }
            }
        }
    }

    return false;
}

void func(int depth, int cp)
{
    if (depth == 7)
    {
        if (checkConnected())
            result++;
        return;
    }

    for (int p = cp; p < 25; p++)
    {
        int y = p / 5;
        int x = p % 5;
        if (checked[y][x])
            continue;
        checked[y][x] = true;
        func(depth + 1, p);
        checked[y][x] = false;
    }
}

int main(void)
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            cin >> map[i][j];
        }
    }

    func(0, 0);

    cout << result << '\n';

    return 0;
}