[백준] 1941번 소문난 칠공주 (C++, 백트래킹)

DFS로 25개 중 7개를 고르는 조합을 만든다.

7개 원소를 골랐으면 그 중에 4명 이상이 이다솜파인지, 인접한지 확인한 후 ans를 올려준다.

번호를 0~24번까지 붙이면 y좌표는 해당 번호/5, x좌표는 해당 번호%5로 검사하면 된다.

 

복사 배열을 하나 더만들어서 조합으로 뽑은 위치에는 Z로 표시해줬다. 뽑은 수 중 하나 아무거나 넣은 후 근접 BFS를 돌렸을 때 Z의 총 개수가 7이 나오면 된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
string student[5][5];
string carr[5][5];
bool visit[5][5];
int ypos[] = {0,1,0,-1};//오른쪽 아래 왼쪽
int xpos[] = {1,0,-1,0};
int ans;
bool collect[25];


bool check() {
	
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			carr[i][j]=student[i][j];
			visit[i][j] = false;
		}
	}
	bool first = true;
	queue<pair<int, int>> q;
	for (int i = 0; i < 25; i++) {
		if (collect[i]) {
			int y = i / 5;
			int x = i % 5;
			if (first) {
				first = false;
				q.push({ y,x });
				visit[y][x] = true;
			}
			carr[y][x] = 'Z';
		}
	}

	
	
	int cnt = 1;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int yy = y + ypos[k];
			int xx = x + xpos[k];
			if (xx < 0 || yy < 0 || xx >= 5 || yy >= 5)continue;
			if (visit[yy][xx])continue;
			visit[yy][xx] = true;
			if (carr[yy][xx] == "Z") {
				cnt += 1;
				q.push({ yy,xx });
			}
			
		}
	}
	if (cnt == 7)return true;
	else return false;
}

bool checkName() {
	int cnt = 0;
	for (int i = 0; i < 25; i++) {
		if (collect[i]) {
			int y = i / 5;
			int x = i % 5;
			if (student[y][x] == "S")cnt += 1;
		}
	}
	if (cnt < 4)return false;
	return true;
}

void nCr(int idx, int cnt) {
	//cout << idx << endl;
	if (cnt==7 && checkName()) {
		//cout << "조합" << endl;
		if (check()) {
			ans += 1;
		}
		
		return;
	}
	for (int i = idx; i < 25; i++) {
		if (collect[i])continue;
		collect[i] = true;
		nCr(i + 1, cnt + 1);
		collect[i] = false;
	}

}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	freopen("sample_input.txt", "r", stdin);
	string temp;
	for (int i = 0; i < 5; i++) {
		cin >> temp;
		for (int j = 0; j < 5; j++) {
			student[i][j] = temp[j];
		}
	}
	vector<int> v;
	for (int i = 0; i < 25; i++) {
		v.push_back(i);
	}
	//7개 조합 구함
	nCr(0, 0);

	cout << ans << endl;

	return 0;
}