백준 1941 소문난 칠공주 C++

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

오답에서 적었듯이, 일반적인 dfs로는 해결하기 까다로운 문제이다.

우선, 들어오는 입력만으로는 (y/s)여부 만으로는 그 성분의 자리가 어디인지 알 수 없다.

따라서 자리번호를 매겼다.

그리고 그 자리번호를 7개 선택해서, 뽑힌 7개의 자리번호가 인접한 상태이고, S를 4개 이상 포함한다면 카운트를 해주었다.

순서가 구분이 안 되서 생기는 문제는, 자리번호를 조합으로 뽑으면 순서에 상관없이 하나만 뽑히기 때문에 해결된다.

#include<iostream>
#include<string>
#include<queue>
using namespace std;
char m[6][6];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int seat[6][6];
bool isused[25];
int st = 0, arr[8], dis[6][6], map[6][6];
queue<pair<int, int> > q;
int res = 0;
bool endFlag = false;
 
void process() {
    int idx = 0;
    endFlag = false;
    for (int i = 0; i < 5; i++) { //뽑힌 학생의 자리번호 1로
        for (int j = 0; j < 5; j++) {
            if (seat[i][j] == arr[idx]) {
                map[i][j] = 1;
                idx++;
                //if (idx == 7) return; 이 구문 때문에 아래 카운트가 안먹혀서 시간낭비
            }
        }
    }
 
    int sCnt = 0;
    //소영 카운트
    for (int i = 0; i < 5; i++) 
        for (int j = 0; j < 5; j++) 
            if (map[i][j] == 1 && m[i][j] == 'S') sCnt++;
        
    
    if (sCnt < 4) endFlag = true;
}
void init() {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            map[i][j] = 0; //자리번호 배열 초기화
            dis[i][j] = -1; //방문처리 배열
        }
    
}
 
void bfs(pair<int, int> start) {
    q.push(start);
    dis[start.first][start.second]++;
    int cnt = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
            if (dis[nr][nc] >= 0 || map[nr][nc] != 1) continue;
            q.push({ nr, nc });
            cnt++;
            dis[nr][nc] = cnt;
        }
    }
    
    if (cnt == 6) //7명이 붙어 앉은 경우
        res++;
    
}
 
void pick(int k) {
    if (k == 7) { //1. 자리번호 7개 선택
    
        init(); 
 
        process();
        if (endFlag) return;
 
        for (int i = 0; i < 5; i++) 
            for (int j = 0; j < 5; j++) 
                if (map[i][j] == 1 && dis[i][j] < 0) 
                    bfs({ i, j }); 
        
        return;
    }
    
    if (k == 0) st = 0;
    for (int i = st; i < 25; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            pick(k + 1);
            isused[i] = false;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int cnt = 0;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            cin >> m[i][j];
            seat[i][j] = cnt;
            cnt++;
        }
    
    pick(0);
    cout << res;
    return 0;
}