qNow와 qNext를 이용해서 한 단계가 끝난 후, 다음 단계가 진행될 수 있도록 한다.
좌표를 받으면 그 점에 대해 범위를 확장시켜가며 최대 포함 가능 집 개수를 센다.
2가 안됐는데, 3이 되는 경우도 있으니 안된다고 끝내면 안된다.
홈방범 서비스를 제공하기 위해서는 운영 비용이 필요하다.
운영 비용은 서비스 영역의 면적과 동일하며,
운영 비용 = K * K + (K - 1) * (K - 1)
홈방범 서비스를 제공받는 집들은 각각 M의 비용을 지불할 수 있어,
보안회사에서는 손해를 보지 않는 한 최대한 많은 집에 홈방범 서비스를 제공하려고 한다.
도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M, 도시의 정보가 주어진다.
이때, 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고,
그 때의 홈방범 서비스를 제공 받는 집들의 수를 출력하는 프로그램을 작성하라.
제약사항
1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초
2. 도시의 크기 N은 5 이상 20 이하의 정수이다. (5 ≤ N ≤ 20)
3. 하나의 집이 지불할 수 있는 비용 M은 1 이상 10 이하의 정수이다. (1 ≤ M ≤ 10)
4. 홈방범 서비스의 운영 비용은 서비스 영역의 면적과 동일하다.
5. 도시의 정보에서 집이 있는 위치는 1이고, 나머지는 0이다.
6. 도시에는 최소 1개 이상의 집이 존재한다.
[입력]
각 테스트 케이스의 첫 번째 줄에는 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M이 주어진다.
그 다음 줄부터 N*N 크기의 도시정보가 주어진다. 지도에서 1은 집이 위치한 곳이고, 나머지는 0이다.
[출력]
손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때,
그 때의 서비스를 제공 받는 집들의 수를 출력하라.
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int N, M;
int map[20][20] = { 0, };
int used[20][20] = { 0, };
struct Node {
int row, col;
};
queue <Node> qNow;
queue <Node> qNext;
// 좌표를 받으면
// 그 점에 대해서 범위를 확장시켜가며 최대 포함 가능 집 개수를 센다.
// 안된다고 끝내면 안됨 <- 2가 안됐는데 3, 4가 될 수도 있으므로 끝까지!
int BFS(int row, int col) {
int Maxhouse = -1;
memset(used, 0, sizeof(used));
qNow.push({ row,col });
used[row][col] = 1;
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int K = 2;
// 들어온 점에 집이 있을 경우 그걸 포함해서 세어주어야함
int houseCnt = 0;
if (map[row][col]) houseCnt++;
// K의 크기를 N까지만 설정하면 오답 나는 경우가 있다.
// 넉넉하게 설정할 것
while (K<=N+1) {
while (!qNow.empty()) {
Node now = qNow.front();
qNow.pop();
for (int d = 0; d < 4; d++) {
int nr = now.row + dr[d];
int nc = now.col + dc[d];
if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
if (used[nr][nc]) continue;
used[nr][nc] = 1;
if (map[nr][nc]) houseCnt++;
qNext.push({ nr,nc });
}
}
while (!qNext.empty()) {
qNow.push(qNext.front());
qNext.pop();
}
if (houseCnt * M >= K * K + (K - 1) * (K - 1)) {
if (houseCnt > Maxhouse) Maxhouse = houseCnt;
}
K++;
}
while (!qNow.empty()) {
qNow.pop();
}
return Maxhouse;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
}
}
// map위의 모든 좌표에 대해 BFS
int maxValue = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int nowValue = BFS(i, j);
if (nowValue > maxValue) maxValue = nowValue;
}
}
cout << "#" << tc << " " << maxValue << "\n";
}
return 0;
}