[백준/BOJ] 백준 1941번 : 소문난 칠공주

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

1941번: 소문난 칠공주

학생 7명을 골라보고, 그 학생들 중 4명 이상이 이다솜파이고, 7명이 가로 세로로 연결되어 있는지 확인하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

vector<string> board;
int discovered[5][5];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//고른 7명이 이다솜파 학생 4명이상으로 구성되어 있는지 확인
bool sCheck(vector<pair<int, int>> selected)
{
	int num = 0;
	for (int i = 0; i < selected.size(); i++)
	{
		if (board[selected[i].first][selected[i].second] == 'S')
			num++;

		if (num >= 4)
			return true;
	}
	return false;
}

//고른 7명이 인접해 있는지 확인
bool cCheck(vector<pair<int, int>> selected)
{
	memset(discovered, 0, sizeof(discovered));

	vector<int> check_selected_number(25, 0); //전체 학생들을 0~24 사이의 숫자로 표현

	for (int i = 0; i < selected.size(); i++)
	{
		int this_selected_number = selected[i].first * 5 + selected[i].second;
		check_selected_number[this_selected_number] = 1; //고른 학생들은 체크
	}

	discovered[selected[0].first][selected[0].second] = 1;

	int cnt = 0;
	queue<pair<int, int>> q;

	q.push(selected[0]); //selected[0]학생부터 탐색 시작

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		cnt++;//인접한 학생 체크

		if (cnt == 7) //7명이 모두 인접할때
			return true;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			if (there.first >= 0 && there.first < 5 && there.second >= 0 && there.second < 5 && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;

				int there_number = there.first * 5 + there.second;
				if (check_selected_number[there_number] == 1) //인접한 학생이 고른 학생중에 있을때
				{
					q.push(there);
				}
			}
		}
	}


	return false;
}

int Solve(vector<pair<int, int>>& selected, int last_selected_number)
{
	//7명을 골랐을때
	if (selected.size() == 7)
	{
		//4명이상이 이다솜파이고, 7명이 가로 세로로 인접해 있을때
		if (sCheck(selected) && cCheck(selected))
			return 1;
		else
			return 0;
	}

	int ret = 0;

	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			int selected_number = i * 5 + j;

			//중복된 선택을 피하기 위한 조건
			if (last_selected_number < selected_number)
			{
				selected.push_back(make_pair(i, j));
				ret += Solve(selected, selected_number);
				selected.pop_back();
			}
		}
	}

	return ret;
}

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

	string input;
	vector<pair<int, int>> selected;

	for (int i = 0; i < 5; i++)
	{
		cin >> input;
		board.push_back(input);
	}

	cout << Solve(selected, -1);

	return 0;
}