백준 1941 소문난 칠공주 (C++)

1941번: 소문난 칠공주

조합과 bfs를 이용한 문제이다. 문제에서 요구하는 것은 해당 조건을 만족하는 경우의 수이다. 그렇기에 조합을 이용해 경우의 수를 먼저 구한 후 해당 경우가 조건에 만족하는지 확인을 해주면 된다. 주어지는 배열의 크기는 5x5이므로 이는 일차원 배열로 나타낼 수 있다. 일차원 배열을 dfs를 통해 조합으로 나타내어 7개가 될 경우 S>=4인지 확인한 후 bfs를 통해 가로 세로로 인접해있는지 확인을 해준다. 일차원 배열에서 이차원 배열로 옮길때는 해당 일차원 배열의 인덱스를 idx라고 할 때, 이차원 배열은 행은 idx / 5, 열은 idx % 5 를 만족한다. 인접해있을 경우 카운트를 해주고 이를 출력해주었다.
생각보다 어려웠던 문제였다. 처음에는 단순히 bfs를 통해 조건을 만족하는 수를 구해주면 된다고 생각했는데 이렇게 구하게될 경우 중복되는 경우가 생기게 된다. 그렇기에 조합을 통해 먼저 좌석을 구해준 후 인접하는지 확인을 하는 방식으로 고쳐 통과하게 되었다. 조합을 이용하는 방식에 대해서도 인지하고 있어야 겠다,

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

string A[5];
bool check[5][5];
int result = 0;
bool combination[25];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

bool bfs(int idx) {
    memset(check, 0, sizeof(check));

    queue<pair<int, int>> q;
    int count = 0;

    q.push({ idx / 5, idx % 5 });
    check[idx / 5][idx % 5] = true;

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        count++;

        if (count == 7) return true;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5) continue;
            if (!combination[ny * 5 + nx]) continue;
            if (check[ny][nx]) continue;

            q.push({ ny,nx });
            check[ny][nx] = true;
        }
    }

    return false;
}

void dfs(int cnt, int depth, int S) {
    if (cnt == 7) {
        if (S >= 4) {
            if (bfs(depth)) result++;
        }
        return;
    }

    for (int i = depth; i < 25; i++) {
        if (combination[i]) continue;

        combination[i] = true;
        dfs(cnt + 1, i, S + (A[i / 5][i % 5] == 'S'));
        combination[i] = false;
    }
}

void solution() {
    dfs(0, 0, 0);

    cout << result;
}

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

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

    solution();

    return 0;
}