[1941] 소문난 칠공주

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

1941번: 소문난 칠공주

<문제>

백트래킹으로 풀면 3방향 이상의 교차로를 재방문해줄 일이 있어서 방문처리가 까다롭다.

25C7개의 경우의 수를 만들고, 해당 경우의 수가 정답의 가능성이 존재하는지를 판정하는 문제로 바꿔 푸는게 편하다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

using pi = pair<int, int>;

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

char a[6][6];

int ans;

bool vst[5][5], tar[5][5];

typedef struct {

    int y, x;

} state;

pi c(int idx) { return {idx / 5, idx % 5}; }

void f(vector<int>& v) {

    memset(vst, 0, sizeof(vst));

    queue<state> q;

    int i, cntS = 0, cntY = 0;

    for (i = 0; i < 25; i++) {

        if (v[i] == 1) {

            pi cur = c(i);

            q.push({cur.first, cur.second});

            vst[cur.first][cur.second] = true;

            cntS += a[cur.first][cur.second] == 'S';

            cntY += a[cur.first][cur.second] == 'Y';

            break;

        }

    }

    while (!q.empty()) {

        state cur = q.front();

        q.pop();

        for (i = 0; i < 4; i++) {

            int y = cur.y + dy[i];

            int x = cur.x + dx[i];

            if (y < 0 || x < 0 || y >= 5 || x >= 5) continue;

            if (tar[y][x] == false) continue;

            if (vst[y][x] == false) {

                vst[y][x] = true;

                q.push({y, x});

                cntS += a[y][x] == 'S';

                cntY += a[y][x] == 'Y';

            }

        }

    }

    if (cntS + cntY == 7) {

        if (cntS >= 4) {

            ans++;

        }

    }

    return;

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    int i, j;

    for (i = 0; i < 5; i++)

        for (j = 0; j < 5; j++) cin >> a[i][j];

    vector<int> base(25, 0);

    for (i = 0; i < 7; i++) base[i] = 1;

    sort(base.begin(), base.end());

    do {

        memset(tar, 0, sizeof(tar));

        for (i = 0; i < 25; i++) {

            if (base[i] == 0) continue;

            pi t = c(i);

            tar[t.first][t.second] = true;

        }

        f(base);

    } while (next_permutation(base.begin(), base.end()) == true);

    cout << ans;

    return 0;

}