[백준] 1941 - 소문난 칠공주

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

1941번: 소문난 칠공주

 

처음에 문제의 접근법을 깨닫지 몰라서 풀이를 참고하였다.

핵심은 제한이 그렇게 크지 않다는 것이었다.

학생의 수는 항상 25명이고, S를 최소 4개 이상, 총 7명 선택하면 된다.

즉 25C7 * (조건에 맞는지 탐색) 만큼의 복잡도가 걸리게 된다.

 

조건에 맞는지 탐색하는 부분은

1. S를 4명 이상 뽑았는가
   • 뽑은 7자리를 모두 탐색한다.
2. 총 7명이 이어져 있는가
   • bfs를 돌려서 서로 이어져 있는지 확인한다.

이다.

 

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

int map[5][5];
int x[4] = { 0,0,1,-1 };
int y[4] = { 1,-1,0,0 };
vector<int> v(25);
bool b1() {
	int ret = 0;
	for (int i = 0; i < 25; i++) {
		if (v[i] && map[i / 5][i % 5])ret++;
	}
	return ret >= 4;
}
bool b2() {
	int cnt = 0;
	queue<int> q;
	int visit[25] = { 0, };
	for (int i = 0; i < 25; i++) {
		if (v[i]) {
			q.push(i);
			visit[i] = 1;
			break;
		}
	}
	while (!q.empty()) {
		int a = q.front(); q.pop();
		cnt++;
		for (int k = 0; k < 4; k++) {
			int nx = a / 5 + x[k];
			int ny = a % 5 + y[k];
			if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !visit[nx * 5 + ny] && v[nx * 5 + ny]) {
				visit[nx * 5 + ny] = 1;
				q.push(nx * 5 + ny);
			}
		}
	}
	return cnt == 7;
}
int main() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			char c; cin >> c;
			if (c == 'Y')map[i][j] = 0;
			else map[i][j] = 1;
		}
	}
	v[0] = v[1] = v[2] = v[3] = v[4] = v[5] = v[6] = 1;
	sort(v.begin(), v.end());
	int ans = 0;
	do {

		if (b1() && b2()) {
			ans++;
		}

	} while (next_permutation(v.begin(), v.end()));
	cout << ans;
}

Reference

https://yabmoons.tistory.com/117