


백준 1941 소문난 칠공주
백준 1941 소문난 칠공주
2022년 12월 4일
2022년 12월 4일
cpp, 완전 탐색
문제
문제
풀이
풀이
임의의 학생 A에 대해 해당 학생을 기준으로 인접한 학생들을 탐색해 나가며 7명의 공주 멤버를 찾는다.
만약, 학생 A에 대해 7공주의 조건에 부합한 학생들을 탐색해 나가는 식으로 문제를 접근한다면 해당 경우의 수를 처리하기 불편하다.

입력으로 주어지는 양이 많지 않으므로, 해당 입력에서 구성할 수 있는 모든 경우의 수에 대해 탐색을 진행한다. 어떤 경우의 수에 대해, 7공주에 부합한 조건을 만족한다면 ans를 더해 나가는 식으로 문제를 해결한다.
코드
코드
#include <bits/stdc++.h>
using namespace std;
string board[5];
int ans;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
for(int i=0; i<5; ++i)
cin >> board[i];
// 25명 학생 중 7명 선택
vector<bool> brute(25);
fill(brute.begin(),brute.begin()+7,1);
queue<pair<int,int>> q;
// 25명에 대해 7명의 학생을 고르는 모든 경우의 수 탐색
do{
for(int i=0; i<25; ++i)
if(brute[i]){
int cnt = 1, y_cnt = 0;
bool vis[5][5] = {0,};
vis[i/5][i%5] = true;
if(board[i/5][i%5] == 'Y') ++y_cnt;
q.push({i/5,i%5});
while(!q.empty()){
auto [x,y] = q.front(); q.pop();
for(int dir=0; dir<4; ++dir){
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx<0||ny<0||nx>=5||ny>=5) continue;
if(!brute[nx*5+ny]) continue;
if(vis[nx][ny]) continue;
if(board[nx][ny] == 'Y'){
// 임도연 파는 3명까지 가능
if(y_cnt >= 3) continue;
++y_cnt;
}
q.push({nx,ny});
vis[nx][ny] = true;
cnt++;
}
}
// 7공주가 완성되면 ans++
if(cnt == 7) ans++;
break;
}
}while(prev_permutation(brute.begin(),brute.end()));
cout << ans;
}
결과
결과

Copyright © 2024 Hyunghoon Kim