[1941번 소문난 칠공주] - C++

[1941번 소문난 칠공주]
https://www.acmicpc.net/problem/1941

풀이

첫 번째 접근, DFS로 한 방향으로 쭉 나아가면서 7명이 될 때까지 탐색. 7명이 되면 S가 4명 이상인지 확인.
-> 실패
이유 : ㄱ,ㄴ 모양의 자리는 탐색이 가능하지만 ㅏ,ㅓ,ㅜ,ㅗ 와 같은 모양은 중간에 분기해야 하기 때문에 한 방향으로만 탐색하는 dfs로는 불가능

두 번째 접근, 25C7 개의 조합 경우의 수로 살펴봄. 약 48만 개 정도이기 때문에 시간 안에 돌 수 있다고 판단. 48만 개의 경우의 수를 하나씩 확인하며 S가 4개 이상인지 확인
-> 실패
이유 : 자리가 서로 인접해야 한다는 조건이 위배되는 경우가 생김

세 번째 접근, 25C7 개의 경우의 수를 돌며, 각 경우의 수마다 S가 4개 이상인지 그리고 BFS를 사용하여 인접한 7개의 자리로 이루어져 있는지 확인.
-> 성공

C++ 코드

#include <bits/stdc++.h>

#define ll long long
using namespace std;
typedef pair<int,int> pint;
typedef vector<int> vint;
const int INF = 0x3f3f3f3f; const int mINF = 0xc0c0c0c0;
const ll LINF = 0x3f3f3f3f3f3f3f3f; const ll mLINF = 0xc0c0c0c0c0c0c0c0;

int ans;
char room[6][6];
int dr[4] = {-1,0,1,0}, dc[4] = {0,1,0,-1};
int vi[6][6];
int s,y;

int bfs(int r, int c) {
	queue<pint> q;
	q.push({r,c});

	int v[6][6];
	memset(v,0,sizeof(v));
	v[r][c] = 1;
	int cnt = 1;

	int nr,nc;
	while(!q.empty()) {
		pint p = q.front(); q.pop();
		r = p.first;
		c = p.second;

		for(int d=0;d<4;++d) {
			nr = r + dr[d];
			nc = c + dc[d];

			if(0<=nr&&nr<5 && 0<=nc&&nc<5 
				&& vi[nr][nc] 
				&& !v[nr][nc]) {
				v[nr][nc] = 1;
				q.push({nr,nc});
				cnt++;
			}
		}
	}

	return cnt;
}

void dfs(int cnt, int idx) {
	if(y >= 4) return;
	if(cnt == 7 && s>=4) {
		if(bfs((idx-1) / 5, (idx-1) % 5) == 7) {
			ans++;
		}
		return;
	}

	int nr,nc;
	for(int i=idx;i<25;++i) {
		nr = i / 5;
		nc = i % 5;

		vi[nr][nc] = 1;
		if(room[nr][nc] == 'S') {
			s++;
			dfs(cnt+1,i+1);
			s--;
		} else {
			y++;
			dfs(cnt+1,i+1);
			y--;
		}
		vi[nr][nc] = 0;
	}

	return;
}

void sol() {
	dfs(0,0);

	return;
}

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) {
			scanf(" %c", &room[i][j]);
		}
	}
	sol();
	printf("%d\n", ans);
	return 0;
}

실행결과