백준 1941번 소문난 칠공주

문제 링크입니다: https://www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

T 자 모양 같이 단순 DFS, BFS 알고리즘을 통해서는 도출해낼 수 없는 경우의 수가 있기 때문에 모든 경우의 수를 도출해낸 후 조건을 충족하는지 확인해야하는 문제였습니다.

5 * 5의 정사각형 격자 형태로 자리가 배치되어있고 여기서 7명을 뽑아야하므로 25C7 가지 즉, 480,700 가지의 경우의 수를 고려해보면 된다는 것을 알 수 있습니다.

따라서, 모든 경우의 수를 고려하더라도 충분히 시간 안에 결과를 구할 수 있습니다.

 

	#include <iostream>
	#include <string>
	#include <cstring>
	using namespace std;
	const int MAX = 5;
	const int PRINCESS_MAX = 7;
	typedef struct
	{
	int y, x;
	}Dir;
	Dir moveDir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };
	int result;
	string classMates[MAX];
	bool visited[MAX][MAX];
	bool colored[MAX][MAX];
	void color(int y, int x)
	{
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= MAX || nextX < 0 || nextX >= MAX)
	{
	continue;
	}
	if (visited[nextY][nextX] == false || colored[nextY][nextX])
	{
	continue;
	}
	colored[nextY][nextX] = true;
	color(nextY, nextX);
	}
	}
	void func(int y, int x, int S, int Y, int cnt)
	{
	// 기저 사례: 임도연파가 우위
	if (Y >= 4)
	{
	return;
	}
	if (cnt == PRINCESS_MAX && S >= 4)
	{
	int colorCnt = 0;
	for (int i = 0; i < MAX; i++)
	{
	for (int j = 0; j < MAX; j++)
	{
	if (visited[i][j] == false || colored[i][j])
	{
	continue;
	}
	colored[i][j] = true;
	colorCnt++;
	color(i, j);
	}
	}
	memset(colored, false, sizeof(colored));
	result = (colorCnt == 1) ? result + 1 : result;
	return;
	}
	for (int i = y; i < MAX; i++)
	{
	for (int j = (i == y ? x : 0); j < MAX; j++)
	{
	if (visited[i][j])
	{
	continue;
	}
	visited[i][j] = true;
	func(i, j, classMates[i][j] == 'S' ? S + 1 : S, classMates[i][j] == 'Y' ? Y + 1 : Y, cnt + 1);
	visited[i][j] = false;
	}
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 0; i < MAX; i++)
	{
	cin >> classMates[i];
	}
	func(0, 0, 0, 0, 0);
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2019

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~