[SWEA] 홈 방범 서비스

SWEA 홈 방범 서비스 C++ 풀이

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

 

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX = 21;

int map[MAX][MAX];
bool visit[MAX][MAX];

int n, m, answer;

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

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

void bfs(int a, int b) {
	int house_cnt = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(a, b));
	visit[a][b] = true;

	if (map[a][b] == 1) house_cnt++;
	int service = 1;

	while (!q.empty()) {
		if (service > n + 1) break;

		if (house_cnt * m - company_benefit(service) >= 0) answer = max(answer, house_cnt);

		int size = q.size();

		for (int s = 0; s < size; s++) {
			int x = q.front().first;
			int y = q.front().second;
			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 < n && ny < n) {
					if (visit[nx][ny] == false) {
						visit[nx][ny] = true;
						q.push(make_pair(nx, ny));
						if (map[nx][ny] == 1) house_cnt++;
					}
				}

			}
		}
		service++;

	}

}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	for (int tc = 1; tc <= t; tc++) {
		answer = 0;
		memset(map, 0, sizeof(map));
		memset(visit, false, sizeof(visit));

		cin >> n >> m;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> map[i][j];
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				bfs(i, j);
				memset(visit, false, sizeof(visit));
			}
		}

		cout << "#" << tc << " " << answer << "\n";

	}



}