[SWEA] 홈 방범 서비스

[SWEA] 홈 방범 서비스

Problem URL : 홈 방범 서비스

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

using namespace std;

int n, m;
int home;
int cost;
int stage;
int map[20][20];
int visited[20][20];
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int ans;

struct Node {
	int y;
	int x;
	int stage;
	Node(int _y, int _x, int _stage) : x(_x), y(_y), stage(_stage) {};
};

int calc() {
	int _cost;
	_cost = m * home - stage * stage - (stage - 1) * (stage - 1);
	return _cost;
}

bool outRange(int y, int x) {
	if (y < 0 || y >= n || x < 0 || x >= n) {
		return true;
	}
	return false;
}

int main() {
	int TC;
	scanf("%d", &TC);
	for (int tc = 1; tc <= TC; tc++) {
		scanf("%d %d", &n, &m);
		memset(visited, 0, sizeof(visited));
		cost = 0;
		ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				memset(visited, 0, sizeof(visited));
				queue <Node> q;
				stage = 1;
				home = 0;
				q.push(Node(i, j, 1));
				int index = 0;
				while (!q.empty()) {
					int y = q.front().y;
					int x = q.front().x;
					int _stage = q.front().stage;
					q.pop();
					if (visited[y][x])
						continue;
					visited[y][x] = 1;
					// 스테이지가 갱신되기 직전이 이익의 최댓값이므로 ans를 계산해준다.
					if (_stage > stage) {
						if (calc() >= 0) {
							ans = ans > home ? ans : home;
						}
						stage = _stage;
					}
					if (map[y][x]) {
						home++;
					}
					for (int k = 0; k < 4; k++) {
						int ny = y + dir[k][0];
						int nx = x + dir[k][1];
						if (outRange(ny, nx) || visited[ny][nx])
							continue;
						q.push(Node(ny, nx, _stage + 1));
					}
					index++;
					// 마지막 전체구간(n * n)을 탐색했을 때 ans를 계산해준다.
					if (index == n * n) {
						if (calc() >= 0) {
							ans = ans > home ? ans : home;
						}
						break;
					}
				}
			}
		}
		printf("#%d %d\n", tc, ans);
	}
	return 0;
}