728x90
https://www.acmicpc.net/problem/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;
}
728x90
'BAEKJOON' 카테고리의 다른 글
BAEKJOON 1615번: 교차개수세기 (0) | 2023.03.18 |
---|---|
BAEKJOON 16367번: TV Show Game (0) | 2023.02.22 |
BAEKJOON 12728: n제곱 계산 (0) | 2023.02.17 |
BAEKJOON 구슬 탈출 1~3 (0) | 2023.02.14 |
BAEKJOON 14426번: 접두사 찾기 (feat. Trie) (0) | 2023.02.02 |