BOJ 1941 : 소문난 칠공주

풀이 상세

완전 탐색 문제

풀이 요약

1. 이다솜 파 가 생존 하는 수단은 총 2가지이다.

   • 여학생 가운데 7명을 추렸을 때 이다솜 파가 4명 이상이어야 한다.
   • 4명 이상인 구성원이 모두 인접해야한다.

2. 배열에 인덱스를 매기고, 조합을 통해 임의의 7명을 고른다. 이후 7명을 통해 DFS 탐색 하여, 이다솜 파 인원이 4명 이상이면서, 그 구성이 모두 인접하다고 확인될 때, 경우의 수를 추가해준다.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
char arr[5][5];
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, -1, 0, 1}, cnt, dist, ans;
vector<int> v;
bool visited[5][5];

void dfs(int r, int c) {
    visited[r][c] = false;
    arr[r][c] == 'S' && cnt++, dist++;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5 || !visited[nr][nc]) continue;
        dfs(nr, nc);
    }
}

void comb(int idx) {
    if (v.size() >= 7) {
        memset(visited, false, sizeof(visited));
        cnt = 0;
        dist = 0;
        for (int i = 0; i < 7; i++) {
            int r = v[i] / 5, c = v[i] % 5;
            visited[r][c] = true;
        }
        dfs(v[0]/5, v[0]%5);
        if (cnt >= 4 && dist >= 7) ans++;
        return;
    }

    for (int i = idx; i < 25; i++) {
        v.push_back(i);
        comb(i + 1);
        v.pop_back();
    }
}

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

void output() {
    cout << ans;
}

int main() {
    input();
    comb(0);
    output();
}