[SWEA] #2117 _ 홈 방범 서비스

[홈 방범 서비스] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

bfs를 이용하여 마름모를 구하였고, 마름모가 커질 때마다 집의 개수를 갱신해주었다.

좌표의 모든 지점을 서비스의 시작 좌표로 모든 경우의 수를 고려하여 가장 많은 집을 구하였다.

 

주의할 점은 손해를 보지 않고 서비스 가능한 최대 집의 수를 구하는 것이기 때문에,

이익이 0이라도 손해를 보지 않는 것이므로 이때 집의 수도 고려해주어야 한다.

 

[ 소스 코드 ]

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define MAX 20

using namespace std;

int dx[] = { 0,1,0,-1 }, dy[] = { -1,0,1,0 };
int N, M, maxHouse;
int map[MAX][MAX], chk[MAX][MAX];

void solve(int x, int y);
int calcCost(int k);
int main() {
	int t_c;

	scanf("%d", &t_c);
	for (int i = 1; i <= t_c; i++) {
		scanf("%d %d", &N, &M);
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				scanf("%d", &map[j][k]);
			}
		}

		maxHouse = 1;
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				solve(k, j);
				memset(chk, 0, sizeof(chk));
			}
		}

		printf("#%d %d\n", i, maxHouse);
	}

	return 0;
}

void solve(int x, int y) {
	queue<pair<int, int> > q;
	pair<int, int> tmp;
	int count = 0, preVal = 0, t_x, t_y;

	q.push(make_pair(y, x));
	chk[y][x] = 1;
	while (!q.empty()) {
		tmp = q.front();
		q.pop();

		if (preVal != chk[tmp.first][tmp.second]) {
			preVal = chk[tmp.first][tmp.second];
			if (preVal >= 2) {
				if (calcCost(preVal - 1) <= M * count) maxHouse = max(maxHouse, count);
			}
		}
		if (map[tmp.first][tmp.second] == 1) count++;
		if (chk[tmp.first][tmp.second] > N) continue;

		for (int i = 0; i < 4; i++) {
			t_x = tmp.second + dx[i];
			t_y = tmp.first + dy[i];
			if (t_x < 0 || t_y < 0 || t_x >= N || t_y >= N) continue;
			if (chk[t_y][t_x] != 0) continue;
			q.push(make_pair(t_y, t_x));
			chk[t_y][t_x] = chk[tmp.first][tmp.second] + 1;
		}
	}
	if (calcCost(preVal) <= M * count) maxHouse = max(maxHouse, count);
}

int calcCost(int k) {
	return k * k + (k - 1)*(k - 1);
}