[백준 1941] 소문난 칠공주 (C++)

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

1941번: 소문난 칠공주

1. 주의할 점

- 전부 S를 입력했을 때, 3546이 나와야 한다

- 이다솜파인 학생이 4명 이상 있어야 한다

 

2. 구현

- DFS와 백트레킹을 통해 구현한다

- DFS(idx,lee,lim) 함수를 통해 각 학생들을 V 벡터에 저장하고, Lee>Lim인 경우에만 V 벡터에 저장된 학생들이 모두 붙어있는지 확인한다

- Check_near() 함수를 통해 각 벡터들이 서로 인접해 있는지 확인한다

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
char arr[5][5];
int check[25], result = 0;
struct info {
	int x, y;
};
info tmp;
vector<info> v;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

bool check_near() {
	queue<info> q;
	bool flag[7] = { false, };
	tmp.x = v[0].x;
	tmp.y = v[0].y;
	q.push(tmp);
	flag[0] = true;
	int cnt = 1;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		q.pop();
		for (int k = 1; k < 7; k++) {
			if (flag[k]) continue;
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];				
				if (nx == v[k].x && ny == v[k].y) {
					tmp.x = nx;
					tmp.y = ny;
					q.push(tmp);
					flag[k] = true;
					cnt++;
				}
			}
		}
	}
	if (cnt == 7) return true;
	else return false;
}

void dfs(int idx, int lee, int lim) {
	if (lee + lim == 7) {
		if (lim > lee) return;
		if (check_near())
			result++;
		return;
	}
	for (int i = idx; i < 25; i++) {
		if (check[i]) continue;
		int r = i / 5;
		int c = i % 5;
		tmp.x = c;
		tmp.y = r;
		v.push_back(tmp);
		check[i] = 1;
		if (arr[r][c] == 'Y')
			dfs(i + 1, lee, lim + 1);
		else
			dfs(i + 1, lee + 1, lim);
		check[i] = 0;
		v.pop_back();
	}
}

int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	string str;
	for (int i = 0; i < 5; i++) {
		cin >> str;
		for (int j = 0; j < 5; j++) 
			arr[i][j] = str[j];		
	}
	dfs(0, 0, 0);
	cout << result;
	system("pause");
	return 0;
}