[백준/C++] 1941. 소문난 칠공주

문제

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

1941번: 소문난 칠공주

총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

 

풀이

[결론]

25개 중에 7개를 뽑는 모든 조합을 구해서, 해당 조합에 대한 조건(이다솜파가 4명 이상인지, 모두 인접해 있는지)을 확인해서 조건에 만족하는 경우를 세면 된다.

 

[시도 1] 

DFS를 이용한 백트래킹을 했다. 결과는 틀렸습니다 였다. 

반례를 확인해보니 DFS의 경우 + 이런 십자 모양의 케이스는 잡아낼 수 없었다. \

 

[시도 2] 

모든 조합을 구해서, 조건을 확인했다. 

7공주가 모두 인접해 있는지 확인할 때, 주먹구구식으로 7공주 자리의 상하좌우에 다른 7공주가 있는지 확인했는데 또 틀렸다!

반례를 확인해보니 7공주가 모두 인접해 있지 않고 두개-세개 덩어리로 나오는 경우가 있었다.

 

[시도 3 (결론)]

모든 조합을 구해서, 조건을 확인하는데 BFS를 이용했다. 

조금이나마 시간복잡도를 줄이기 위해서, 조합을 뽑는 중간에 임도연파(Y)가 4명 이상이되면 해당 케이스는 더 이상 진행하지 않고 버렸다. 

 

모든 조합의 갯수가 25C7 = 480,700 밖에 되지 않아서 모든 조합을 다 검사해도 시간초과가 나지 않았다. 

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

char table[5][5];
int cache[5][5];
int answer = 0;

int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };

bool isOk(vector<int> selected) {
	fill(&cache[0][0], &cache[4][5], 0);
	for (int i = 0;i < 7;i++) {
		cache[selected[i] / 5][selected[i] % 5] = 2; // 7공주 자리 표시
	}

	queue<pair<int, int>> q;
	q.push({ selected[0] / 5, selected[0] % 5 });
	cache[selected[0] / 5][selected[0] % 5] = 1;
	int remain = 6; 

	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++) {
			int newR = r + dr[i];
			int newC = c + dc[i];

			if (newR < 0 || newR>4 || newC < 0 || newC>4) continue;

			// 방문한 적이 없는 7공주 자리이면 
			if (cache[newR][newC] == 2) { 
				remain--;
				cache[newR][newC] = 1;
				q.push({ newR, newC });
			}
		}
	}
	// BFS탐색을 완료했는데, 7공주를 모두 찾았다 -> 모두 인접해있다.
	if (remain == 0)
		return true;
	else 
		return false;
}
// 0~24 (25개) 에서 7개 뽑기 
void combi(int start, int doyean, int count, vector<int> selected) {
	if (count == 7) {
		if (isOk(selected)) answer++;
		return;
	}
	if (table[start / 5][start % 5] == 'Y') doyean++;
	for (int i = start+1;i < 25;i++) {
		if (table[i / 5][i % 5] == 'Y') {
			// 도연파가 4명 이상이 되면 더 이상 진행x
			if (doyean + 1 > 3) continue;
		}
		selected.push_back(i);
		combi(i, doyean, count + 1, selected);
		selected.pop_back();
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	for (int i = 0;i < 5;i++) {
		for (int j = 0;j < 5;j++) {
			cin >> table[i][j];
		}
	}

	for (int i = 0;i < 25;i++) 
		combi(i, 0, 1, {i});
	
	cout << answer << endl;
	return 0;
}

결과