[BOJ] 소문난 칠공주(1941)

[백준(BOJ)] 1941_소문난 칠공주 C++

문제 : BOJ_1941번 소문난 칠공주

문제 설명

5 * 5의 map이 주어지고, 각 자리는 'Y' 혹은 'S'로 표현되어 있습니다.

위, 아래, 좌, 우에 서로 인접한 7개의 자리에서 'S' 가 최소 4개 이상 있는 7 자리의 수를 찾는 문제입니다.

---

Solution

완전 탐색, bfs

각 자리에 대한 정보를 벡터에 저장해 줍니다.

저장할 정보는 각 자리의 위치, 'S'인지의 여부입니다.

저장된 상태에서 7개의 자리를 check 해주고 이 7개의 자리에서 'S'가 4개 이상인 경우 bfs를 돌려줍니다.

bfs에서 다음을 확인하며 순회해 줍니다.

• 주어진 크기 안에 있는 map의 자리인지
• 좌, 우, 상, 하로 인접돼있는지
• 앞선 완전 탐색에서 check 되어 있는 자리인지
  
  이 조건을 만족하며 check된 7개의 자리를 모두 순회한 경우에 답에 추가해 줍니다.

---

Description

• 25C7 = 480,700이고 bfs로 7개를 push 하기 때문에 시간 복잡도가 크지 않습니다.
• check 하는 각 요소는 lot이라는 pair 배열을 선언하여 위치 좌표를 저장했습니다.

---

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
char map[6][6];
int s_chk[26];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int cnt_m = 1;
void go(int idx, int cnt);
int chk[26];
int res,swc;
void go_res();
int lot[26][26];
vector<pair<int, int>> v;
int main(void) {
    v.resize(26);
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            scanf(" %c", &map[i][j]);
            if (map[i][j] == 'S') s_chk[cnt_m] = 1;
            lot[i][j] = cnt_m;
            v[cnt_m] = { i,j };
            cnt_m++;
        }
    }
    go(1, 1);
    printf("%d\n", res);
}
void go(int idx, int cnt) {
    if (cnt == 8) {
        int das = 0;
        swc = 0;
        for (int i = 1; i <= 25; i++) {
            if (chk[i]) {
                if (s_chk[i]) {
                    das++;
                    if (!swc) swc = i;
                }
            }
        }
        if (das >= 4) go_res();
        return;
    }
    for (int i = idx; i <= 25; i++) {
        if (chk[i]) continue;
        chk[i] = 1;
        go(i, cnt + 1);
        chk[i] = 0;
    }
}
void go_res(void) {
    int go = 0;
    int vis[26][26];
    memset(vis, 0, sizeof(vis));
    queue<pair<int,int>> q;
    q.push({ v[swc].first, v[swc].second });
    vis[v[swc].first][v[swc].second] = 1;
    while (!q.empty()) {
        go++;
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || ny < 1 || nx>5 || ny>5) continue;
            if (vis[nx][ny]) continue;
            if (chk[lot[nx][ny]]==1) {
                vis[nx][ny] = 1;
                q.push({ nx,ny });
            }
        }
    }
    if (go == 7) {
        res++;
    }
}