[BOJ 1941] 소문난 칠공주

김동근·2021년 1월 26일
0

문제

BOJ 1941 소문난 칠공주

유형

  • 조합

풀이

모든 좌표를 순회하면서 DFS로 풀이하려고 하였지만 방향이 여러군데로 퍼지있는 모양을 찾는 구현을 하지 못하였다.

예를들어 이런 경우

00000
00100
11110
01010
00000

그래서 다시 생각해보니 전체 크기가 5*5 밖에 되지 않기 때문에 25C7 연산도 값이 그렇게 크지 않을 것이라고 생각되었다.

전체에서 7개를 무작위롤 뽑은 뒤 Y가 3개 이하로 포함되어 있으면서 서로 접해있는 경우를 찾으면 정답을 얻을 수 있었다.

  1. 25개 중 7개 뽑는 조합 구성
    1-1 Y가 4개 이상이면 바로 탈출
  2. BFS를 이용하여 7개의 원소가 서로 접해 있는지 확인
  3. 조건을 만족하면 정답++

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

string arr[5];
set<pair<int, int>> s;
int ans = 0;

void solve(vector<int>& v) {
	set<int> temp;
	for (int x : v) temp.insert(x);

	queue<int> q;
	bool visited[5][5] = { false, };
	q.push(v[0]);
	visited[v[0] / 5][v[0] % 5] = true;
	int cnt = 1;
	while (!q.empty()) {
		int x = q.front() % 5;
		int y = q.front() / 5;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5 || visited[ny][nx]) continue;
			else if (temp.count(ny * 5 + nx) == 1) {
				visited[ny][nx] = true;
				cnt++;
				q.push({ ny * 5 + nx });
			}
		}
	}

	if (cnt == 7) ans++;
}

void permutation(int d, vector<int>& v) {
	int len = v.size();
	if (len >= 4) {
		int c = 0;
		for (int i = 0; i < len; i++) {
			int x = v[i] % 5;
			int y = v[i] / 5;
			if (s.count({ x ,y }) == 0) c++;
		}
		if (c >= 4) return;
	}

	if (len == 7) {
		
		solve(v);
		return;
	}
	else if (d == 25) return;
	else {
		v.push_back(d);
		permutation(d + 1, v);
		v.pop_back();
		permutation(d + 1, v);
	}
}

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

	for (int i = 0; i < 5; i++) {
		cin >> arr[i];
		for (int j = 0; j < 5; j++) {
			if (arr[i][j] == 'S') s.insert({ j, i }); // x y
		}
	}

	vector<int> t;
	permutation(0, t);

	cout << ans;
	return 0;
}
profile
김동근

0개의 댓글