1941 소문난 칠공주

문제 링크

dfs나 bfs로 풀 수 없는 문제로 n = 25, m = 7

n!(n−m)!∗m!=480700

임을 활용하여 제한된 시간 내로 전수 조사하여 풀 수 있다.

생성된 숫자의 연결을 확인하여 풀 수 있었다.

#include <bits/stdc++.h>

using namespace std;

int n[7], ans;
string d;

int isConnected() {
    int t[5][5], v[5][5], r = 0, c, cnt = 0;
    int rD[] = { -1, 1, 0, 0 };
    int cD[] = { 0, 0, -1, 1 };

    memset(t, 0, sizeof(t));
    memset(v, 0, sizeof(v));
    for (int i = 0; i < 7; i++) {
        r = (n[i] != 0) ? (n[i] / 5) : 0;
        c = n[i] % 5;
        t[r][c] = 1;
    }

    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) {
        queue<pair<int, int>> q;
        if (t[i][j]) {
            q.push(make_pair(i, j));
            v[i][j] = 1;
            while (!q.empty()) {
                cnt++;
                int row = q.front().first;
                int col = q.front().second;
                q.pop();
                for (int i = 0; i < 4; i++) {
                    int nRow = row + rD[i];
                    int nCol = col + cD[i];
                    if (nRow < 0 || nCol < 0 || nRow >= 5 || nCol >= 5) continue;
                    if (v[nRow][nCol] || !t[nRow][nCol]) continue;
                    q.push(make_pair(nRow, nCol));
                    v[nRow][nCol] = 1;
                }
            }
            if (cnt == 7)
                return 1;
            else
                return 0;
        }
    }
    return 0;
}

int chk() {
    int sCnt = 0;
    for (int i = 0; i < 7; i++) {
        if (d[n[i]] == 'S')
            sCnt++;
    }
    if (sCnt >= 4) {
        if (isConnected()) {
            return 1;
        }
    }
    return 0;
}

void solve(int st, int d) {
    if (d == 7) {
        if (chk()) {
            ans++;
        }
        return;
    }

    for (int i = st; i < 25; i++) {
        n[d] = i;
        solve(i + 1, d + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string z;
    for (int i = 0; i < 5; i++) {
        cin >> z;
        d += z;
    }

    solve(0, 0);

    cout << ans << "\n";
}

다른 사람 풀이

#include <bits/stdc++.h>
using namespace std;

char A[7][7];
int ans, d[4] = { 0,0,1,-1 };
bool chk[7][7], visited[7][7];

void dfs(int x, int y) {
    visited[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int xx = x + d[i], yy = y + d[3 - i];
        if (xx < 1 || yy < 1 || xx > 5 || yy > 5 || !chk[xx][yy] || visited[xx][yy]) continue;
        dfs(xx, yy);
    }
}

bool ok() {
    int cnt = 0;
    memset(visited, 0, sizeof(visited));
    for (int i = 1; i <= 5; i++) for (int j = 1; j <= 5; j++) {
        if (chk[i][j] && !visited[i][j]) dfs(i, j), cnt++;
    }
    if (cnt > 1) return 0;
    int c1 = 0, c2 = 0;
    for (int i = 1; i <= 5; i++) for (int j = 1; j <= 5; j++) if (chk[i][j]) {
        if (A[i][j] == 'S') c1++;
        else c2++;
    }
    return c1 > 3;
}

void f(int x, int y) {
    if (y > 7) return;
    if (x == 25) {
        if (y == 7) ans += ok();
        return;
    }
    f(x + 1, y);
    chk[x / 5 + 1][x % 5 + 1] = 1;
    f(x + 1, y + 1);
    chk[x / 5 + 1][x % 5 + 1] = 0;
}

int main() {
    for (int i = 1; i <= 5; i++) scanf("%s", A[i] + 1);
    f(0, 0);
    printf("%d\n", ans);
}