2117. [모의 SW 역량테스트] 홈 방범 서비스

#include<iostream>
#include<cstdio>
#include<queue> #include<utility>
#include<cstring> #include<cstdlib>
using namespace std;


int tc;
int n, m;
int map[20][20];
int v[22][22];
int dd[22];
int cost[22];
int ans = 0;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void initial();

void making_secu(int x, int y) {
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	int cnt = map[x][y];
	v[x][y] = 1;
	while (!q.empty()) {
		x = q.front().first; y = q.front().second;
		q.pop();
		if (v[x][y] > n + 1) return;
		if (map[x][y]) dd[v[x][y]]++;
		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 && v[nx][ny] == false) {
				q.push(make_pair(nx, ny));
				v[nx][ny] = v[x][y] + 1;
			}
		
		}
	}

}
int checking() {
	int sum = 0;
	int h = 0;
	for (int i = 0; i <= n + 1; i++)
	{
		sum += dd[i];
		if (cost[i] <= sum * m) {
			h = sum;
		}
	}
	return h;
}


int main() {
	cin >> tc;
	for (int i = 1; i <= 21; i++) {
		cost[i] = i * i + (i - 1) * (i - 1);
	}

	for (int t = 1; t <= tc; t++) {
		ans = 0;
		initial();
		cin >> n >> m;
		vector<pair<int, int>> home;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> map[i][j];
				if (map[i][j] == 1) {
					home.push_back(make_pair(i, j));
				}
			}
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				making_secu(i, j);
				ans = ans < checking() ? checking() : ans ;
				memset(dd, 0, sizeof(dd));
				memset(v, 0, sizeof(v));
			}
		}


		cout << '#' << t << ' ' <<ans<< endl;
	}
	return 0;
}



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

재밌었던 문제, 전형적인 BFS문제가 아닐까? 마름모그리는데, for문으로 할수도있겠지만 시간을 너무많이잡아먹을듯