[백준 1941번] 소문난 칠공주

문제 링크: https://www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

<문제 풀이> 백트랙킹

5X5 격자에서 7자리를 뽑아서(2차원 배열에서 조합) BFS로 연결 여부 확인 + S의 개수가 4 이상인지 확인하면 됩니다.

 

2차원 배열 조합

 for (int i = s; i < 25; i++) {

        int x = i / 5;

        int y = i % 5;

        res[x][y] = 1;

        dfs(i + 1, k + 1);

        res[x][y] = 0;

    }

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
#define X first
#define Y second
 
int res[5][5];
int dx[4] = {0, 0, 1, -1};
int dy[4] = { -1, 1, 0, 0 };
bool visited[5][5];
vector<vector<char> > v(5);
int cnt = 0;
 
void dfs(int s, int k) {
    if (k == 7) {
        int temp = 0;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (res[i][j] == 1 && v[i][j] == 'S') {
                    temp++;
                }
            }
        }
        if (temp >= 4) {
 
            int connected = 0;
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    if (res[i][j] == 1 && !visited[i][j]) {
                        queue<pair<int, int> > Q;
                        Q.push({ i, j });
                        visited[i][j] = true;
                        while (!Q.empty()) {
                            auto cur = Q.front(); Q.pop();
                            for (int dir = 0; dir < 4; dir++) {
                                int nx = cur.X + dx[dir];
                                int ny = cur.Y + dy[dir];
                                if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5)continue;
                                if (visited[nx][ny] || res[nx][ny] == 0)continue;
                                Q.push({ nx, ny });
                                visited[nx][ny] = true;
                            }
                        }
                        connected++;
                    }
                }
            }
            if (connected == 1) cnt++;
        }
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                visited[i][j] = 0;
            }
        }
        return;
    }
 
    for (int i = s; i < 25; i++) {
        int x = i / 5;
        int y = i % 5;
        res[x][y] = 1;
        dfs(i + 1, k + 1);
        res[x][y] = 0;
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
   
    for (int i = 0; i < 5; i++) {
        string s; cin >> s;
        int s_len = s.length();
        v[i].resize(5);
        for (int j = 0; j < s_len; j++) {
            v[i][j] = s[j];
        }
    } 
    dfs(0, 0);
    cout << cnt;
   
 
    return 0;
}