[Baekjoon] 14502 - 연구소 (C++)

https://www.acmicpc.net/problem/14502

14502번: 연구소

벽이 세워질 수 있는 모든 경우의 수를 고려하여 풀었습니다. 매번 벽을 세운 뒤에 바이러스를 확산시킨 후, 빈 공간을 계산하는 방식으로 풀면 됩니다. 입력으로 들어오는 지도의 크기가 크지 않기 때문에 가능한 방법입니다. 바이러스를 확산시키는 방법으로는 DFS(depth-first search) 알고리즘을 이용했습니다.

 

대략적인 풀이 방법은 다음과 같습니다.

1. 지도를 입력받으면서 빈 공간의 좌표와 바이러스의 좌표를 따로 기록
2. 원본 지도를 복사한 새로운 지도를 만든 뒤에 벽을 세움
3. DFS 알고리즘을 이용해 바이러스 확산
4. 남아있는 빈 공간을 계산
5. 위 2 ~ 4 과정을 벽을 세울 수 있는 모든 경우의 수에 대해 반복하면서 빈 공간의 최댓값을 찾고 출력

위 방법으로 한 번에 통과할 수 있었습니다. 따로 주의할 부분이 있다면 바이러스를 확산시키는 과정에서 배열의 인덱스 오류가 발생하지 않도록 예외 처리를 잘 하거나 배열의 크기를 늘려주는 부분이 있겠군요.

#include <iostream>
#include <vector>

using namespace std;

class Point
{
public:
	int x;
	int y;

	Point(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
};

int map[8][8];
int n, m;

vector<Point> emptyList;
vector<Point> virusList;

void DFS(int cMap[8][8], int x, int y)
{
	cMap[y][x] = 2;

	if (y > 0 && cMap[y - 1][x] == 0) DFS(cMap, x, y - 1);
	if (y < n - 1 && cMap[y + 1][x] == 0) DFS(cMap, x, y + 1);
	if (x > 0 && cMap[y][x - 1] == 0) DFS(cMap, x - 1, y);
	if (x < m - 1 && cMap[y][x + 1] == 0) DFS(cMap, x + 1, y);
}

int getEmptySize(const Point& p1, const Point& p2, const Point& p3)
{
	int cMap[8][8];
	int emptySize = 0;

	// 지도 복사
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cMap[y][x] = map[y][x];
		}
	}

	// 벽 세우기
	cMap[p1.y][p1.x] = 1;
	cMap[p2.y][p2.x] = 1;
	cMap[p3.y][p3.x] = 1;
	
	// DFS 알고리즘을 이용해 바이러스 확산
	for (const auto& virusPos : virusList) {
		DFS(cMap, virusPos.x, virusPos.y);
	}

	// 남아있는 빈 공간 계산
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			if (cMap[y][x] == 0) emptySize++;
		}
	}

	return emptySize;
}

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

	int maxEmptySize = 0;
	cin >> n >> m;

	// 지도 입력 및 빈 공간과 바이러스의 좌표 기록
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> map[y][x];

			if (map[y][x] == 0) emptyList.push_back(Point(x, y));
			else if (map[y][x] == 2) virusList.push_back(Point(x, y));
		}
	}

	// 벽을 세울 수 있는 모든 경우의 수를 계산한 뒤 빈 공간의 최댓값 계산
	for (int i = 0; i < emptyList.size() - 2; i++) {
		for (int j = i + 1; j < emptyList.size() - 1; j++) {
			for (int k = j + 1; k < emptyList.size(); k++) {
				int emptySize = getEmptySize(emptyList[i], emptyList[j], emptyList[k]);
				if (maxEmptySize < emptySize) maxEmptySize = emptySize;
			}
		}
	}
	
	cout << maxEmptySize << "\n";
	return 0;
}