[ boj : 1941 ] 소문난 칠공주

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

1941번: 소문난 칠공주

문제 : 읽고 오세요 ㅠㅠ 

해설 : 어우우우우우ㅜ울ㅇ눌ㄴ울 ....이런문제 한번 말리면 끝도 없이 말려서 너무 힘드네요 ㅠㅠ

처음에는 그냥 dfs+백트래킹 인줄 알았는데...이렇게 되면 현재 있는 위치에서만 갈수있는데를 바라볼뿐 다른 칸으로는 나아가지 못하는 문제가 있습니다.

XXOXX

OOOOO

XXOXX

XXXXX

XXXXX

이런 경우는 전혀 찾지를 못하게 되는 것이죠 ㅠㅠㅠ 그래서 방법을 바꾸었습니다. 그냥 미리 7개를 뽑아놓고 이 7개 중 'S'가 4개 이상인지 그리고 전부 연결되어 있는지를 확인하는 로직으로요...이게 제일 마음이 편한 것 같습니다.

선택한 정점들이 전부 연결되어있는지 확인하는 방법은 disjoint-set 개념을 적용시켜 부모의 정보들을 확인하며 체크할 수 있습니다.

#include<bits/stdc++.h>

using namespace std;

bool visit[25];
int ans,parent[7];
string board[5];
set<int> s;

void cb(int n, int r);
bool solve();
void union_parent(int x, int y);
int get_parent(int x);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	for (int i = 0; i < 5; i++)
		cin >> board[i];
	cb(25, 7);
	
	cout << ans;
	return 0;
}
void cb(int n, int r)
{
	if (r == 0) {
		if (solve()) {
			ans++;
		}
		return;
	}
	else if (n < r)return;
	
	visit[n - 1] = true;
	cb(n - 1, r - 1);

	visit[n - 1] = false;
	cb(n - 1, r);
}
bool solve()
{
	vector<pair<int, int>> v;
	int num = 0, cnt = 0;
	int memo[5][5], check1[5][5];
	int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };


	for (int i = 0; i < 25; i++)
		if (visit[i]) {
			if (board[i / 5][i % 5] == 'S')cnt++;
			v.push_back({i/5,i%5});
		}
	if (cnt < 4)return false;
	
	for (int i = 0; i < 7; i++)parent[i] = i;

	for (int i = 0; i < 7; i++)
		for (int j = i + 1; j < 7; j++)
			if (abs(v[i].first - v[j].first) + abs(v[i].second - v[j].second) <= 1)
				union_parent(i, j);
	for (int i = 0; i < 7; i++)
		if (get_parent(0) != get_parent(i))
			return false;
	return true;
}
void union_parent(int x, int y)
{
	x = get_parent(x);
	y = get_parent(y);

	parent[y] = x;
}
int get_parent(int x)
{
	if (x == parent[x])return x;
	return parent[x] = get_parent(parent[x]);
}