[코드트리] 방화벽 설치하기

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/firewall-installation/description?page=1&pageSize=20

💻 문제 풀이 : C++

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

#define MAP_SIZE 10

using namespace std;

struct Coord {
	int row;
	int col;
};

int n, m;
int MAP[MAP_SIZE][MAP_SIZE];
int TMP_MAP[MAP_SIZE][MAP_SIZE];

int visited[MAP_SIZE][MAP_SIZE];
int used[MAP_SIZE*MAP_SIZE];

int dr[] = {0, 0, -1, 1};
int dc[] = {-1, 1, 0, 0};

int maxAns;
vector<Coord> voidSpace;
vector<Coord> wall;
queue<Coord> fire;

int getSafeArea()
{
	int area = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (TMP_MAP[i][j] == 0)
				area++;
		}
	}
	return area;
}

void copyOrigMap()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			TMP_MAP[i][j] = MAP[i][j];
		}
	}
}

void INPUT()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> MAP[i][j];
			if (MAP[i][j] == 0)
			{
				voidSpace.push_back({ i, j });
			}
			else if (MAP[i][j] == 2)
			{
				fire.push({ i, j });
			}
		}
	}
}

void simulation()
{
	memset(visited, 0, sizeof(visited));
	queue<Coord> temp;
	temp = fire;
	while (!temp.empty())
	{
		Coord now = temp.front();
		temp.pop();
		for (int i = 0; i < 4; i++)
		{
			int nR = now.row + dr[i];
			int nC = now.col + dc[i];
			if (nR < 0 || nC < 0 || nR >= n || nC >= m) continue;
			if (TMP_MAP[nR][nC] != 0) continue;
			if (visited[nR][nC] == 1) continue;
			visited[nR][nC] = 1;
			TMP_MAP[nR][nC] = 2;
			temp.push({ nR, nC });
		}
	}
}

void pickWall(int depth)
{
	if (depth >= 3)
	{
		copyOrigMap();
		for (int i = 0; i < 3; i++)
		{
			TMP_MAP[wall[i].row][wall[i].col] = 1;
		}
		simulation();
		maxAns = max(maxAns, getSafeArea());
		return;
	}
	for (int i = 0; i < voidSpace.size(); i++)
	{
		if (used[i] == 1) continue;
		used[i] = 1;
		wall.push_back(voidSpace[i]);
		pickWall(depth + 1);
		wall.pop_back();
		used[i] = 0;
	}
}

int main()
{
	INPUT();

	pickWall(0);

	cout << maxAns << endl;

	return 0;
}

---

📌 memo 😊

Queue 복사하기 ('=' 연산자 사용)

queue<int> a;
queue<int> b;
b = a;