Baekjoon 14502 - 연구소

💫 문제

---

🫧 Example Input/Output

// IN
7 7 // N, M
2 0 0 0 1 1 0 // 각 칸 정보
0 0 1 0 1 2 0 // 0 = 빈칸
0 1 1 0 1 0 0 // 1 = 벽
0 1 0 0 0 0 0 // 2 = 바이러스
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
// OUT
27 // 최대 안전 구역 수

💫 C++ 풀이

---

#include <bits/stdc++.h>
using namespace std;

const int MX = 10;
int world[MX][MX];
bool canMove[MX][MX];

int n, m;

int sim()
{
	queue<pair<int, int>> q;

	// Init
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			canMove[i][j] = world[i][j] == 0;

			if (world[i][j] == 2)
			{
				q.push({i, j});
			}
		}
	}

	// BFS
	while (q.empty() == false)
	{
		pair<int, int> cur = q.front();
		q.pop();

		int r = cur.first;
		int c = cur.second;

		if (r - 1 >= 0 && canMove[r - 1][c])
		{
			canMove[r - 1][c] = false;
			q.push({r - 1, c});
		}

		if (r + 1 < n && canMove[r + 1][c])
		{
			canMove[r + 1][c] = false;
			q.push({r + 1, c});
		}

		if (c - 1 >= 0 && canMove[r][c - 1])
		{
			canMove[r][c - 1] = false;
			q.push({r, c - 1});
		}

		if (c + 1 < m && canMove[r][c + 1])
		{
			canMove[r][c + 1] = false;
			q.push({r, c + 1});
		}
	}

	// Result
	int emptyCount = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (canMove[i][j])
			{
				emptyCount++;
			}
		}
	}

	return emptyCount;
}

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

	cin >> n >> m;

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

	int maxCoord = n * m;
	int maxVirus = 0;

	for (int first = 0; first < maxCoord; first++)
	{
		int firstY = first % m;
		int firstX = first / m;

		if (world[firstX][firstY] != 0)
			continue;

		world[firstX][firstY] = 1;

		for (int second = first + 1; second < maxCoord; second++)
		{
			int secondY = second % m;
			int secondX = second / m;

			if (world[secondX][secondY] != 0)
				continue;

			world[secondX][secondY] = 1;

			for (int third = second + 1; third < maxCoord; third++)
			{
				int thirdY = third % m;
				int thirdX = third / m;

				if (world[thirdX][thirdY] != 0)
					continue;

				world[thirdX][thirdY] = 1;

				maxVirus = max(maxVirus, sim());

				world[thirdX][thirdY] = 0;
			}

			world[secondX][secondY] = 0;
		}

		world[firstX][firstY] = 0;
	}

	cout << maxVirus;
}

💫 Memo

---

🫧 문제 정리

• 3 <= N, M <= 8
• 2 <= 바이러스 수 <= 10

• 3 <= 빈칸 수

• N*M 월드
  • 0 : 빈 칸
  • 1 : 벽
    • 벽 3개를 새로 세운다
  • 2 : 바이러스
    • 바이러스는 상하좌우 퍼져나간다

바이러스가 없는 곳 안전 영역

🫧 풀이

• 3중 for문
  1. 3개의 벽을 세우고
  2. 바이러스 BFS
  3. 최대 안전 영역 = max(최대 안전 영역, 현재 안전 영역)

🫧 메모

• Column Row 신경쓸 것
• 1151 -> 1156