BAEKJOON 1941번: 소문난 칠공주

 

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

1941번: 소문난 칠공주

들어가며..

오른쪽은 이 문제의 태그다. 풀고 나서 보니 신기한게 많지만.. 그냥 백트래킹 문제이다.

 

풀이

우리가 표현해야 하는 공간은 고작 5×5 사이즈이다.

따라서 경우의 수는 고작 $2^{25}=33554432$이므로, 충분히 통과할 수 있다.

그리고 사실 저 만큼의 경우의 수를 탐색하지도 않는다. 탐색을 진행할 때 현재 선택한 칸에서 인접한 칸으로만 방문할 것이며, 임도연 파에 속한 학생이 3명을 초과하면 탐색을 중단할 것이기 때문이다.

 

무식하게 백트래킹을 구현하고 $2^{25}$ 크기의 배열을 생성하여 문제의 조건을 만족하는 경우 중 중복되는 경우를 걸러주면 된다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
char A[10][10];
bool D[(1<<25)];
int idx(int i,int j){
    return(i-1)*5+j-1;
}
int f(int k,int t,int bit){
    if(t>3||D[bit])return 0;
    if(k>=7){
        D[bit]=true;
        return 1;
    }
    int ret=0;
    for(int x=1;x<=5;x++)for(int y=1;y<=5;y++){
        if(!(bit&(1<<idx(x,y))))continue;
        if(x<5&&!(bit&(1<<idx(x+1,y))))ret+=f(k+1,t+(A[x+1][y]=='Y'),bit|(1<<idx(x+1,y)));
        if(y<5&&!(bit&(1<<idx(x,y+1))))ret+=f(k+1,t+(A[x][y+1]=='Y'),bit|(1<<idx(x,y+1)));
        if(x>1&&!(bit&(1<<idx(x-1,y))))ret+=f(k+1,t+(A[x-1][y]=='Y'),bit|(1<<idx(x-1,y)));
        if(y>1&&!(bit&(1<<idx(x,y-1))))ret+=f(k+1,t+(A[x][y-1]=='Y'),bit|(1<<idx(x,y-1)));
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++)cin>>A[i][j];
    }
    int ans=0;
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++)ans+=f(1,(A[i][j]=='Y'),(1<<idx(i,j)));
    }
    cout<<ans;
    return 0;
}