백준 1941번 : 소문난 칠공주 - 백트래킹 C++

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

1941번: 소문난 칠공주

 

1. 문제설명

25명의 학생 중 7명을 뽑아보는 백트래킹을 진행하면서

7명 중 4명이상이 S인지 확인하고,

7명이 모두 인접해있는지 BFS 탐색을 해서

옳으면 경우의 수를 추가해주면 된다.

 

 

2. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int ans = 0;
string arr[5];
bool student[25];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool check() {
    int num = 0;
    int x, y;
    
    for (int i = 0; i < 25; i++) {
        if (student[i]) {
            int row = i / 5;
            int col = i % 5;

            if (arr[row][col] == 'S') {
                num++;
                x = row;
                y = col;
            }

        }
    }
    if (num < 4) return false;
    
    queue<pair<int, int> > Q;
    Q.push({x, y});
    int cnt = 1;

    bool vis[5][5] = {0};
    vis[x][y] = 1;

    while (!Q.empty()) {
        int curx = Q.front().first;
        int cury = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = curx + dx[i];
            int ny = cury + dy[i];

            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5)continue;
            if (vis[nx][ny]) continue;
            if (!student[nx * 5 + ny]) continue;

            vis[nx][ny] = 1;
            Q.push({nx, ny});
            cnt++;
        }
    }


    return cnt == 7;
}


void DFS(int idx, int num) {
    if (num == 7) {
        if (check()) {
            ans++;
        }
        return;
    }

    for (int i = idx; i < 25; i++) {
        student[i] = 1;
        DFS(i + 1, num + 1);
        student[i] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    DFS(0, 0);
    cout << ans << '\n';

    return 0;
}