[백준 1941] 소문난 칠공주

[백준 1941] 소문난 칠공주

문제 링크

#include "header.h"
using namespace std;
char classroom[10][10];
int visit[30];
int ans;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
void input() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> classroom[i][j];
        }
    }
}

bool bfs(int x, int y) {

    int q_visit[10][10];
    memset(q_visit, 0, sizeof(q_visit));

    queue<pair<int, int>> q;
    q.push({x, y});
    q_visit[x][y] = 1;
    int cnt = 1;

    while (!q.empty()) {
        int topx = q.front().first;
        int topy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = topx + dx[i];
            int ny = topy + dy[i];
            if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5 || q_visit[nx][ny]) continue;

            if (visit[nx * 5 + ny]) {
                cnt++;
                q.push({nx, ny});
                q_visit[nx][ny] = 1;
            }
        }
    }

    if (cnt == 7) return true;
    else return false;
}

void check_adj() {
    for (int i = 0; i < 25; i++) {
        if (visit[i]) {                
            if (bfs(i / 5, i % 5)) {
                ans++;
            }
            return;
        }
    }
}
void dfs(int idx, int cnt, int S) {
    if (cnt == 7 && S >= 4) {
        check_adj();
        return;
    }

    for (int i = idx; i < 25; i++) {
        if (!visit[i]) {
            visit[i] = 1;
            if (classroom[i / 5][i % 5] == 'S')
                dfs(i + 1, cnt + 1, S + 1);
            else
                dfs(i + 1, cnt + 1, S);
            visit[i] = 0;
        }
    }
}
int main() {
    input();
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

• dfs + bfs 문제
• 처음엔 백트래킹으로 접근해서 인접하는 7개 -> count 하는 식으로 했는데, 중복을 처리할 수가 없어서 실패했다.
• 중복 처리를 위해 5*5가 아닌 일차원 배열인 25로 접근했다.
• 7명을 만들 수 있는 모든 경우의 수를 구하고, S가 4개 이상인 경우, 인접한지 확인한다.
• bfs로 인접여부를 확인하고, 모두 인접 했다면 (cnt가 7개라면) 답을 +1 해 준다.