[BOJ] 1941: 소문난 칠공주 (C++) with 조합

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

1941번: 소문난 칠공주

---

 

문제 풀이

14500번 테트로미노가 떠오르는 문제였다.

https://morenow.tistory.com/22

[BOJ] 14500: 테트로미노 (JAVA)

이렇게 격자에서 일부분을 떼어내는 문제는 종종 있었다. 대부분 dfs로 해결하곤 했는데, 테트로미노 문제에선 하나의 조각만 dfs로 해결할 수 없어 따로 처리를 해줬다. 길이 2갈래로 갈라지면 안되는 것이다.

 

소문난 칠공주 문제는 더 심각하다. 하나의 모양만 dfs로 해결할 수 없는 것이 아니라, 대부분이 dfs로 해결할 수 없는 중간에 갈라지는 경우가 발생하는 것이다. 설마 하다가 검색을 해보니 그 설마가 맞았다.

 

너무 많이 나오고, 나올 때마다 골머리를 앓게 하는 "조합" 문제이다. 격자에서 7개만을 골라 모든 조각이 붙어있는지를 확인하면 되는 것이다. 약간은 무식하다고 생각되기도 한다.

 

조합을 쓰게 되면 항상 시간복잡도가 가능한지 실제로 따져봐야 한다. (물론 모든 알고리즘에서 생각해야 하지만...)

이 문제에서는 25C7 = 480,700 이다. 충분히 가능하고도 남는 횟수이다.

 

또한 조합을 쓸 때, 조합을 문자열로 전달하는 것을 좋아했다. 예를 들어, 지금까지 1, 2, 3번이 뽑혔으면 "123" 을 인자로 전달하는 것이다. 그런데 이 경우 0~24 중에서 뽑아야 하므로 문자열이 안돼서 vector<int> 로 전달했다. 사소한 곳에서 시간낭비...

 

이제 실제 풀이 과정을 보자.

1. 25개의 좌표 중 7개를 선택한다. 이 때, (a, b) 형태의 자료를 조합하는 것은 너무 어렵기 때문에, 0~24의 수 중에서 7개를 조합하고, 나온 수를 5로 나눈 몫을 a, 5로 나눈 나머지를 b라 하자.
   예를 들어, 17 이라는 수는 5로 나눈 몫이 3이고, 나머지가 2이므로 (3, 2)에 대응된다.
2. 조합이 완료되면 2가지를 확인해야 한다. 각각을 함수로 구현한다.
   1. 좌표 조합이 붙어있는지 확인한다. (adaj 함수)
   2. 이다솜파가 4명 이상인지 확인한다. (manys 함수)
3. 확인되면 ans를 증가시킨다.

#include <bits/stdc++.h>

using namespace std;

string students[5];
int ans;

bool adaj(vector<int>& cand) {
	bool check[7] = {0};
	queue<int> q;
	q.push(cand[0]);
	check[0] = true;
	while(!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 1; i < 7; i++) {
			if (check[i]) continue;
			int diff = cand[i] - cur;
			if (diff * diff== 1 || diff * diff == 25) {
				if (cur % 5 == 4 && cand[i] % 5 == 0 || cur % 5 == 0 && cand[i] % 5 == 4) continue;
				q.push(cand[i]);
				check[i] = true;;
			}
		}
	}
	for (int i = 0; i < 7; i++)
		if (!check[i]) return false;
	return true;
}

bool manys(vector<int>& cand) {
	int snum = 0;
	for (int i = 0; i < 7; i++) {
		if (students[cand[i]/5][cand[i]%5] == 'S')
			snum++;
	}
	if (snum >= 4) return true;
	else return false;
}

void comb (int idx, vector<int> cand) {
	if (cand.size() == 7) {
		if (adaj(cand) && manys(cand)) {
			ans++;
		}
		return;
	}
	if (idx == 25) return;
	cand.push_back(idx);
	comb(idx+1, cand);
	cand.pop_back();
	comb(idx+1, cand);
}

int main(void) {
	for (int i = 0; i < 5; i++)
		cin >> students[i];
	vector<int> v;
	comb(0, v);
	cout << ans;
	return 0;
}