백준 1941번 - 소문난 칠공주 (C++)

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

1941번: 소문난 칠공주

 

처음에는 dfs 백트레킹 완전 탐색으로 풀어내려 했다. 그러나 백트레킹 완전탐색은 ㅗ ㅏ ㅜ ㅓ 같은 모양은 나타낼 수 없다. 이러한 문제를 테트로미노 문제에선 길이가 4밖에 안되었으니 위 4개의 모양만 따로 관리하면 되었으나 이 문제는 길이가 7이기 때문에 따로 관리하는 것이 불가능하다. 

 

풀이 방법은 다음과 같다.

1. 총 25명의 학생 중 7명을 뽑는다 -> 조합으로 0번~24번 중 7개를 뽑는다.

2. 번호를 좌표화 한다. ( N / 5 , N % 5 )

3. 뽑은 좌표들의 파벌을 조사한다. 이다솜 파벌이 인원이 더 많으면 이들이 인접한지 검사한다.

 

조합은 dfs를 활용해 조합하였고 인접한지 검사도 dfs를 활용했다. 되게 좋은 문제인 것 같다!

 

#include<iostream>
#include<vector>
#define MAX 25
using namespace std;

char team[6][6];
int temp[6][6] = { 0, };
bool visited[MAX] = { false, };
bool check[7] = { false, };
int S = 0;
int Y = 0;

int answer = 0;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

vector<pair<int, int>> princess;

void init() {
	S = 0;
	Y = 0;
	for (int i = 0; i < 7; i++) {
		check[i] = false;
	}
}

void check_dfs(int idx) {
	int x = princess[idx].first;
	int y = princess[idx].second;

	for (int i = 0; i < 4; i++) {
		int nextx = x + dx[i];
		int nexty = y + dy[i];

		for (int j = 0; j < 7; j++) {
			if (nextx == princess[j].first && nexty == princess[j].second && check[j] == false) {
				check[j] = true;
				check_dfs(j);
			}
		}
	}
}

void dfs(int idx, int cnt) {
	if (cnt == 7) {
		for (int i = 0; i < MAX; i++) {
			if (visited[i] == true) {
				princess.push_back({ i / 5, i % 5 });
				if (team[i / 5][i % 5] == 'S')
					S++;
				else
					Y++;
			}
		}

		if (S >= 4) {
			check[0] = true;
			check_dfs(0);
			int cnt = 0;
			for (int i = 0; i < 7; i++) {
				if (check[i] == true)
					cnt++;
			}

			if (cnt == 7)
				answer++;
		}
		
		init();

		princess.clear();
		return;
	}

	for (int i = idx; i < MAX; i++) {
		if (visited[i] == true) continue;
		visited[i] = true;
		dfs(i, cnt + 1);
		visited[i] = false;
	}
}

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

	for (int i = 0; i < 5; i++) {
		string tmp;
		cin >> tmp;
		for (int j = 0; j < 5; j++) {
			team[i][j] = tmp[j];
		}
	}
	dfs(0, 0);

	cout << answer << '\n';
}