SWEA 2117. 홈 방범 서비스 (C++)

모옹·2023년 2월 18일
0

알고리즘

목록 보기
5/18

요약

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;
}

0개의 댓글