백준 BOJ 1941 - 소문난 칠공주

ㅂUSACO 문제풀이

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

1941번: 소문난 칠공주

힌트를 유심히 봐야할 필요가 있는 문제

얼핏 보기에는 매우 dfs/bfs 문제같이 생겨먹었지만

위 사진에서의 두번째 힌트에서 보듯
dfs/bfs로는 "Y" 자 탐색을 진행할 수 없기 때문에

다른 접근이 필요하다.

 

전체 판이 25칸으로 만들어져 있고, 이중에 '소문난 칠공주'의 7개 칸이 반드시

자리하고 있어야 하기 때문에,

"브루트포스 알고리즘" 이라는 태그에 맞게

25개 칸 중 7개의 칸을 선택하는 모든 경우의 수인 25C7 = 480700가지 경우를

모두 탐색해주면 된다.

 

칸의 선택은 next_permutation 이나 prev_permutation 함수를 사용해서 구현했다.

 

이렇게 7개의 칸을 선택했을 때,

이 7개의 칸 중에 이다솜파의 갯수를 세준 다음,

 

이 칸들이 서로 인접해 있지 않아 문제에서 요구하는

조건과 맞지 않은 경우가 발생할 수 있기 때문에,

이 칸들이 서로 인접해있는지 아닌지의 여부를 dfs / bfs 등을 사용해서 구해주도록 하자

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

bool vis[6][6] = {false};
bool pos[30] = {false};
pair<int,int> point;
queue<pair<int,int>> q;

string board[6];

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

bool isconn(){
	memset(vis, 0, sizeof(vis));
	
	int cnt = 1;
	q.push(point);
	vis[point.x][point.y] = true;
	
	while(!q.empty()){
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		
		for(int i=0; i<4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(!(0<=nx&&nx<5) || !(0<=ny&&ny<5)) continue;
			
			if(!vis[nx][ny] && pos[nx*5+ny]){
				cnt++;
				q.push({nx,ny});
				vis[nx][ny] = true;
			}
		}
	}
	return cnt == 7;
}

int main(){
	for(int i=0; i<5; i++) cin >> board[i];
	for(int i=0; i<7; i++) pos[i] = true;
	
	int ans = 0;
	int som = 0;
	do{
		som = 0;
		for(int i=0; i<25; i++){
			if(pos[i]){
				point = {i/5, i%5};
				if(board[i/5][i%5] == 'S') som++;
			}
		}
		if(som < 4) continue;
		if(isconn()) ans++;
	}while(prev_permutation(pos,pos+25));
	
	cout << ans;
	return 0;
}