[C++] 백준 1941번: 소문난 칠공주

문제 링크

1941번: 소문난 칠공주

문제 요약

25명의 학생 중에서 7명의 학생들을 뽑는데, 이 뽑힌 학생들은 가로 또는 세로로 인접해서 하나의 그룹을 이뤄야 한다. 이 학생들 중에서 이다솜파 학생이 4명 이상 있도록 할 수 있는 경우의 수를 구해야 한다.

접근 방법

$_{25}C_7=480700$이기 때문에 7명을 뽑는 경우를 모두 탐색해봐도 문제가 없을 것이라고 생각했고, 그 판단이 맞았습니다.

1. 25명 중에 7명을 뽑습니다.
2. 이 7명 중에 이다솜파 학생이 4명 이상인지 세봅니다.
3. 4명 이상이라면, 이들이 모두 인접해 있는지 판단합니다.

서로 인접해 있는지 여부는 BFS로 판단하였습니다. 7명의 학생을 std::set에 저장하고 한 명을 std::queue에 넣었습니다. 그리고 상하좌우에 인접하면서 set 내에 있는 학생을 queue에 넣고 set에서는 삭제했습니다. 이런 식으로 BFS를 돌리고 7명을 모두 탐색할 수 있다면 가능한 경우라고 판단했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n[6][6], res, dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
char b[6][6];
bool visited[26];
pair<int, int> pos[26];
vector<int> v;

void func(int cnt, int idx)
{
	if (cnt == 7)
	{
		int s = 0;
		for (auto& i : v)
			if (b[pos[i].first][pos[i].second] == 'S')
				s++;

		if (s < 4)
			return;

		set<int> tmp;
		for (auto& i : v)
			tmp.insert(i);

		int num = 0;
		queue<int> q;
		q.push(v[0]);
		tmp.erase(v[0]);
		while (!q.empty())
		{
			pair<int, int> now = pos[q.front()];
			q.pop();
			num++;

			for (int i = 0; i < 4; i++)
			{
				int nr = now.first + dir[i][0], nc = now.second + dir[i][1];
				int next = n[nr][nc];

				if (nr >= 1 &&  nr <= 5 && nc >= 1 && nc <= 5 && tmp.find(next) != tmp.end())
				{
					tmp.erase(next);
					q.push(next);
				}
			}
		}

		if (num == 7)
			res++;
		return;
	}

	for (int i = idx; i <= 25; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			v.push_back(i);
			func(cnt + 1, i + 1);
			visited[i] = false;
			v.pop_back();
		}
	}
}

int main(void)
{
	int idx = 1;
	for (int i = 1; i <= 5; i++)
		for (int j = 1; j <= 5; j++)
			cin >> b[i][j], n[i][j] = idx, pos[idx++] = { i, j };

	func(0, 1);
	cout << res;
	return 0;
}