[C++]SW Expert Academy 홈 방범 서비스

문제는 다음과 같다.

오늘은 SW Expert Academy 홈 방범 서비스 문제를 풀어보도록 하자. 홈 방범 서비스는 마름모 형태로만 제공한다고 한다. 처음엔 마름모 모양을 어떻게 구현할지 생각을 했다.

하지만 모양을 구현하는 것이 아니라 BFS의 큐 관리를 통해서 탐색하는 것을 알게되고 쉽게 풀렸다. 다른 BFS와는 달리 큐의 턴 관리를 해주어야 한다. 현재의 큐 사이즈 만큼 for문을 돌리고 탈출하여

방범료를 갱신한 후, 변한 큐 사이즈만큼 for문을 돌리면서 값을 찾아야 한다.

                                     [코드]
#include <iostream>
#include <queue>
using namespace std;
struct pos {
	int y;
	int x;
};
queue<pos>Q;
int N, M, answer = 0;
int map[20][20];
bool visit[20][20];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

void Init_visit() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = false;
		}
	}
}

void Init_map() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] = -1;
		}
	}
}

void bfs() {
	int K = 1, safe_money = 0, house = 0;
	
	if (map[Q.front().y][Q.front().x] == 1) {
		safe_money += M;
		house++;
	}

	while(!Q.empty()){
		int launching_money = K * K + (K - 1)*(K - 1);
		if (safe_money - launching_money >= 0) {
			if (answer < house) {
				answer = house;
			}
		}
		int size_of_Q = Q.size();

		for (int i = 0; i < size_of_Q; i++) {
			int y = Q.front().y;
			int x = Q.front().x;

			Q.pop();

			for (int j = 0; j < 4; j++) {
				int my = y + dir[j][0];
				int mx = x + dir[j][1];

				if (my >= 0 && mx >= 0 && my < N && mx < N) {
					if (!visit[my][mx]) {
						if (map[my][mx] == 1) {
							safe_money += M;
							house++;
						}
						visit[my][mx] = true;
						Q.push({ my,mx });
					}
				}
			}
		}
		K++;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T, num = 0;
	cin >> T;

	while (T--) {
		cin >> N >> M;
		answer = 0;
		
		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++) {
				Q.push({ i,j });
				visit[i][j] = true;
				bfs();
				Init_visit();
			}
		}
		Init_map();
		cout << "#" << ++num << " " << answer << '\n';
	}
}