[백준 1941] 소문난 칠공주

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

1941번: 소문난 칠공주

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
char board[5 + 2][5 + 2];
int ans;

struct _st
{
	int x, y;
};
std::vector<_st> V;
std::vector<int> choice;

std::queue<_st> Q;
int points[5 + 2][5 + 2];
int visited[5 + 2][5 + 2];


void input()
{
	for (int r = 0; r < 5; r++) {
		scanf("%s", &board[r]);
		for (int c = 0; c < 5; c++) {
			V.push_back({ r, c });
		}
	}
}


bool chk_four()
{
	int cnt = 0;
	for (int c : choice) {
		if (board[V[c].x][V[c].y] == 'S') cnt++;
	}
	if (cnt >= 4) return true;
	return false;
}


void BFS(int x, int y)
{
	// dir
	int dir_x[4] = { 0, 0 ,1 ,-1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	// init
	Q = {};

	Q.push({ x, y });
	visited[x][y] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > 5 - 1 || ny < 0 || ny > 5 - 1) continue;
			if (points[nx][ny] == 0) continue;
			if (visited[nx][ny]) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
}



bool chk_conn()
{
	// put points 
	memset(points, 0, sizeof(points));
	for (int c : choice) {
		points[V[c].x][V[c].y] = 1;
	}
	//debug();

	// Flood Fill
	int cnt = 0;
	memset(visited, 0, sizeof(visited));

	for (int r = 0; r < 5; r++) {
		for (int c = 0; c < 5; c++) {
			if (points[r][c] == 0) continue;
			if (visited[r][c]) continue;
			BFS(r, c);
			cnt++;
			if (cnt >= 2) return false;
		}
	}
	return true;
}


void DFS(int n, int cnt)	// 몇번째 벡터, 몇명 뽑음
{
	if (cnt == 7) {
		if (!chk_four()) return;
		if (!chk_conn()) return;
		ans++;
		return;
	}
    if (n == 25) return;


	// 미포함
	DFS(n + 1, cnt);

	// 포함 
	choice.push_back(n);
	DFS(n + 1, cnt + 1);
	choice.pop_back();

}

int main()
{
	input();
	DFS(0, 0);
	printf("%d\n", ans);
	return 0;
}

1. 25개 위치 중 7개 선택 

2. 뽑은 위치들 중 S가 4개 미만이면 리턴 

3. 뽑은 위치들이 인접하지 않으면 리턴 

4. 위의 두 조건 만족하면 ans++;