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

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

쉬운 백트래킹 문제인 줄 알았으나, 여러가지 조건으로 인해 시간을 길게 보낸 문제.

처음에는 DFS를 돌려봤으나 어떤 중간지점에서 끊기는 경우(십자모양)은

탐지하지 못하였다.

따라서 다른 방법이 필요했다.

문제 접근

25명의 학생 중 중 7명을 고르는 경우의 수는 $_{25}C_{7}=480700$이다.

백트래킹으로도 충분히 가능한 경우의 수이고, DFS로는 십자모양을

탐색하지 못하기 때문에

스도쿠에 사용되었던 방법을 사용해

백트래킹을 진행해준다.

백트래킹 시 7명의 학생을 고르고 그 조합이 가능한 조합인지 확인하는

체크 함수를 만들어 체크해준다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int ans=0;
char board[5][5];

bool ck(int x, int y, char tmp[5][5]){
    queue<pair<int, int>> q;
    bool vis[5][5]={0,}; vis[x][y]=1;
    int dx[]={1,-1,0,0},dy[]={0,0,1,-1},acnt=1;
    q.push({x,y});
    while(!q.empty()){
        int cx=q.front().first;
        int cy=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=cx+dx[i];
            int ny=cy+dy[i];
            if(4<nx || nx<0 || 4<ny || ny<0) continue;
            if(tmp[nx][ny]=='.') continue;
            if(vis[nx][ny]) continue;
            q.push({nx,ny});
            vis[nx][ny]=1;
            acnt++;
        }
    }
    if(acnt!=7) return false;
    return true;
}

void backTracking(int x, int y, int scnt, int ycnt, char tmp[5][5]){
    if(scnt+ycnt==7){
        if(ck(x,y,tmp)) ans++;
        return;
    }
    for(int i=x;i<5;i++) for(int j=0;j<5;j++){
            if(i==x && j<=y) continue;
            tmp[i][j]=board[i][j];
            if(tmp[i][j]=='Y' && ycnt<3) backTracking(i,j,scnt,ycnt+1,tmp);
            if(tmp[i][j]=='S') backTracking(i,j,scnt+1,ycnt,tmp);
            tmp[i][j]='.';
    }
    return;
}

void solve(){
    char f[5][5]; for(int i=0;i<5;i++) for(int j=0;j<5;j++) f[i][j]='.';
    for(int i=0;i<5;i++) for(int j=0;j<5;j++){
        f[i][j]=board[i][j];
        if(f[i][j]=='Y') backTracking(i,j,0,1,f);
        if(f[i][j]=='S') backTracking(i,j,1,0,f);
        f[i][j]='.';
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    for(int i=0;i<5;i++) for(int j=0;j<5;j++) cin >> board[i][j];
    solve();
    return 0;
}