[C++] 백준 14502번: 연구소

첫 번째 시도

0인 칸 중 세 칸을 골라 1로 만드는 모든 경우를 저장한다.

그 경우를 모두 순회하며 2인 칸부터 시작하여 너비 우선 탐색을 진행한다.

인접한 칸이 0인 칸을 2로 만들어가며 너비우선탐색을 마치면,

0인 칸의 수를 세어 최대값을 찾는다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	vector<vector<int>> Lab(N, vector<int>(M));
	FOR(r, N) FOR(c, M)
		cin >> Lab[r][c];

	typedef pair<int, int> Vec2;
	
	// Collect all situation 0 to 1
	vector<Vec2> Emptys;
	FOR(r, N) FOR(c, M)
		if (Lab[r][c] == 0)
			Emptys.push_back(make_pair(r, c));
	vector<vector<Vec2>> Walls;
	const int SIZE = Emptys.size();
	for (int e0 = 0; e0 < SIZE; ++e0)
		for (int e1 = 0; e1 < SIZE; ++e1)
			for (int e2 = 0; e2 < SIZE; ++e2)
				Walls.push_back({ Emptys[e0], Emptys[e1], Emptys[e2] });

	// Explore the Lab from 2
	constexpr int adjs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
	int max_safe_area = 0;
	for (auto& sit : Walls) {
		// Set the new walls
		auto Lab_ = Lab;
		for (auto& wall : sit)
			Lab_[wall.first][wall.second] = 1;

		// Add start point that is 2
		queue<Vec2> BFS;
		FOR(r, N) FOR(c, M)
			if (Lab[r][c] == 2)
				BFS.push(make_pair(r, c));
		
		// Explore the Lab_ from 2
		while (BFS.size()) {
			auto& [r, c] = BFS.front();

			for (auto& adj : adjs) {
				int chg_r = r + adj[0];
				int chg_c = c + adj[1];
				if (chg_r < 0 || chg_r >= N) continue;
				if (chg_c < 0 || chg_c >= M) continue;
				if (Lab_[chg_r][chg_c] != 0) continue;
				BFS.push(make_pair(chg_r, chg_c));
				Lab_[chg_r][chg_c] = 2;
			}

			BFS.pop();
		}

		// Count the safe area
		int safe_area = 0;
		FOR(r, N) FOR(c, M)
			if (Lab_[r][c] == 0)
				safe_area++;
		max_safe_area = max(max_safe_area, safe_area);
	}

	cout << max_safe_area << EL;

	return 0;
}

하지만 틀렸다. 예제는 모두 통과했다.

반례 찾기

8 8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

정답은 61이지만 63이 출력된다. 0에서 1로 세 칸을 바꾸는데, 그 세 칸이 모두 같은 경우가 있다는 뜻이다.

코드를 천천히 다시 살펴보니 오류가 있었다. 중첩 반복문에서 초기값이 0이 아니라 그 윗 단계의 +1을 한 값이 들어가야 한다.

vector<vector<Vec2>> Walls;
const int SIZE = Emptys.size();
for (int e0 = 0; e0 < SIZE; ++e0)
	for (int e1 = 0; e1 < SIZE; ++e1)
		for (int e2 = 0; e2 < SIZE; ++e2)
			Walls.push_back({ Emptys[e0], Emptys[e1], Emptys[e2] });

vector<vector<Vec2>> Walls;
const int SIZE = Emptys.size();
for (int e0 = 0; e0 < SIZE; ++e0)
	for (int e1 = e0 + 1; e1 < SIZE; ++e1)
		for (int e2 = e1 + 1; e2 < SIZE; ++e2)
			Walls.push_back({ Emptys[e0], Emptys[e1], Emptys[e2] });

코드

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	vector<vector<int>> Lab(N, vector<int>(M));
	FOR(r, N) FOR(c, M)
		cin >> Lab[r][c];

	typedef pair<int, int> Vec2;
	
	// Collect all situation 0 to 1
	vector<Vec2> Emptys;
	FOR(r, N) FOR(c, M)
		if (Lab[r][c] == 0)
			Emptys.push_back(make_pair(r, c));
	vector<vector<Vec2>> Walls;
	const int SIZE = Emptys.size();
	for (int e0 = 0; e0 < SIZE; ++e0)
		for (int e1 = e0 + 1; e1 < SIZE; ++e1)
			for (int e2 = e1 + 1; e2 < SIZE; ++e2)
				Walls.push_back({ Emptys[e0], Emptys[e1], Emptys[e2] });

	// Explore the Lab from 2
	constexpr int adjs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
	int max_safe_area = 0;
	for (auto& sit : Walls) {
		// Set the new walls
		auto Lab_ = Lab;
		for (auto& wall : sit)
			Lab_[wall.first][wall.second] = 1;

		// Add start point that is 2
		queue<Vec2> BFS;
		FOR(r, N) FOR(c, M)
			if (Lab[r][c] == 2)
				BFS.push(make_pair(r, c));
		
		// Explore the Lab_ from 2
		while (BFS.size()) {
			auto& [r, c] = BFS.front();

			for (auto& adj : adjs) {
				int chg_r = r + adj[0];
				int chg_c = c + adj[1];
				if (chg_r < 0 || chg_r >= N) continue;
				if (chg_c < 0 || chg_c >= M) continue;
				if (Lab_[chg_r][chg_c] != 0) continue;
				BFS.push(make_pair(chg_r, chg_c));
				Lab_[chg_r][chg_c] = 2;
			}

			BFS.pop();
		}

		// Count the safe area
		int safe_area = 0;
		FOR(r, N)
			FOR(c, M)
				if (Lab_[r][c] == 0)
					safe_area++;
		max_safe_area = max(max_safe_area, safe_area);
	}

	cout << max_safe_area << EL;

	return 0;
}

제출 결과