BOJ 1941 - 소문난 칠공주

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	4418	2106	1326	45.693%

문제

---

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

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

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

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

입력

---

'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

출력

---

첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

접근

---

처음엔 그냥 DFS로 7칸씩 잡으면서 구현해보려고 했었다.
하지만, 방문 순서가 다르지만 결과적으로 중복된 칸들을 처리하기가 까다로웠다.

그래서 그냥 숫자 7개를 조합으로 구해서 구현해보기 위해서 시간을 계산해보았다.
25C7 = 480,700 이 나왔다. (물론 구하는 과정에서 더 많은 벡터를 조회해야하긴 한다.)
그 이후 2번, 4번 조건은 상수의 시간에 구할 수 있으므로, 이 방법으로 선택했다.

풀이

---

comb 함수를 통해서 조합을 만들어나갔다.
v의 크기가 7이면 완성된 것이므로, 바로 solve 함수를 실행해주었다.

각 원소들의 y, x 값을 구해서 check 배열에 1로 넣어주었다.
기존에 S = 1, Y = 0으로 저장된 arr 배열을 통해 S를 쉽게 count 할 수 있었다.
당연히 더한 값이 4보다 작으면 바로 탈출해주었다.

마지막으로는 4번 조건을 위해서 한 점에서 DFS를 했다.
cnt가 7이 나오면, 정답값을 1씩 증가시켜줬다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int arr[5][5], ans = 0, check[5][5], cnt;

void DFS(int y, int x)
{
	cnt++;
	check[y][x] = 0;
	FUP(i, 0, 3)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5 || !check[ny][nx]) continue;
		DFS(ny, nx);
	}
}

void solve(vector<int> v)
{
	FUP(i, 0, 4)
	{
		FUP(j, 0, 4)
		{
			check[i][j] = 0;
		}
	}
	int S = 0, y, x;
	for (int num : v)
	{
		y = num / 5;
		x = num % 5;
		S += arr[y][x];
		check[y][x] = 1;
	}
	if (S < 4) return;
	cnt = 0;
	DFS(y, x);
	if (cnt == 7) ans++;
}

void comb(int idx, vector<int> v)
{
	if (v.size() == 7)
	{
		solve(v);
		return;
	}
	if (idx == 25) return;
	FUP(i, idx, 24)
	{
		v.push_back(i);
		comb(i + 1, v);
		v.pop_back();
	}
}

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

	FUP(i, 0, 4)
	{
		FUP(j, 0, 4)
		{
			char tmp;
			CIN(tmp);
			arr[i][j] = tmp == 'S' ? 1 : 0;
		}
	}
	comb(0, {});
	COUT(ans);

	return 0;
}