[C++] 백준/BOJ - 14502 : 연구소

문제 이해 단계

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

3개의 벽을 배치하여 얻을 수 바이러스가 퍼지지 않는 방의 최대 개수를 구하는 문제이다.
바이러스는 십자가 모양으로 퍼지고 벽을 통과할 수 없다.

입력으로 연구소의 지도가 주어지고,
출력으로 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하는 문제이다.

이해 자체는 오래 걸리지 않았던 문제이다.

 

---

문제 접근 단계

이 문제의 포인트는 무조건 3개의 벽을 활용해야 한다는 점과
입력으로 주어지는 N과 M의 크기가 최대 8로 엄청나게 작다.

게다가 시간제한이 2초, 메모리 제한이 512MB로 넉넉하기 때문에
벽 3개를 전부 다 탐색하는 브루트포스 방식을 사용해도 된다고 생각했다.

그리고 바이러스는 십자가 모양으로 한 칸씩 퍼지는 것이고,
벽에는 퍼질 수 없기 때문에, 전형적으로 BFS 방식으로 표현이 가능하다고 생각했다.

그래서 이 문제는 브루트포스 + BFS로 풀면 된다.

1. 벽을 넣을 수 있는 공간에 벽 3개를 모두 넣는다.
2. 바이러스가 퍼지는 BFS를 큐가 빌 때까지 반복한다.
3. 남은 0의 개수를 반환한다.
4. 벽의 위치를 옮긴다.
5. 2~4번을 벽을 넣을 수 있는 모든 공간을 방문할 때까지 반복한다. 

위와 같은 작업을 했을 때, 반환한 0의 개수가 가장 높은 것이 답이 된다.

 

---

문제 구현 단계

int Bfs() {
	queue<pair<int, int>> q = virus;
	int count = 0;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		c[x][y] = true;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > N || ny < 1 || ny > M || map[nx][ny] != 0) continue;
			if (!c[nx][ny]) {
				c[nx][ny] = true;
				q.push(make_pair(nx, ny));
				count++;
			}
		}
	}
	return count;
}

바이러스 확산을 진행하는 BFS함수 부분이다.
일반적인 BFS와 큰 차이는 없다.

여기서 뜻하는 count는 바이러스의 수이다.
방문에 체크하고 큐에 하나씩 넣을 때마다 count++한다.
반환값으로 count를 반환한다.

 

int WorkVirus(pair<int,int> w1, pair<int, int> w2, pair<int, int> w3) {
	for (int i = 1; i <= 8; i++)
		for (int j = 1; j <= 8; j++) c[i][j] = false;

	map[w1.first][w1.second] = 1;
	map[w2.first][w2.second] = 1;
	map[w3.first][w3.second] = 1;

	minVirus = min(minVirus, Bfs());

	map[w1.first][w1.second] = 0;
	map[w2.first][w2.second] = 0;
	map[w3.first][w3.second] = 0;

	return minVirus;
}

지도에 벽을 배치시키고, 바이러스가 가장 적은 배치를 찾는 WorkVirus 함수이다.
매개변수로 벽 3개의 위치를 받는다.

현재 가장 작은 바이러스 개수와
현재 BFS의 결과와 비교하여 가장 작은 것으로 갱신한다.

각 map을 1에서 0으로 바꿔주는 것은
사용이 끝난 벽을 다시 없애주는 것을 뜻한다.

minVirus를 반환한다.

int safety = 0;

	for(int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) {
				list.push_back(make_pair(i, j));
				safety++;
			}
			else if (map[i][j] == 2) virus.push(make_pair(i, j));
		}

	int answer;
	for(int i = 0; i < list.size()-2; i++)
		for(int j = i+1; j < list.size()-1; j++)
			for (int k = j + 1; k < list.size(); k++) {
				answer = WorkVirus(list[i], list[j], list[k]);
			}

	cout << safety - answer-3;

아래는 메인함수 부분이다.]

입력으로 주어진 지도를 완성하고, 바이러스인 2의 위치를 virus 큐에 저장한다.
이는 BFS를 반복적으로 돌려주기 위함이다. 또한 0의 개수를 세어 방의 개수를 파악한다.

이후 브루트포스를 위해 i, j, k를 처음부터 끝까지 돌려준다.

처음부터 끝까지 WorkVirus를 수행하면서, 가장 작은 바이러스의 개수를 반환받는다.
그 후 방의 개수 - (가장 작은 바이러스 개수) - (벽 3개의 개수)를 해줘서 답을 구한다.

마지막으로 전체 코드를 올리고 문제를 끝내겠다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;


int N, M;
int map[9][9];
int c[9][9] = { false };
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
int minVirus = 100000;

queue<pair<int, int>> virus;
vector<pair<int, int>> list;

int Bfs() {
	queue<pair<int, int>> q = virus;
	int count = 0;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		c[x][y] = true;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > N || ny < 1 || ny > M || map[nx][ny] != 0) continue;
			if (!c[nx][ny]) {
				c[nx][ny] = true;
				q.push(make_pair(nx, ny));
				count++;
			}
		}
	}
	return count;
}
int WorkVirus(pair<int,int> w1, pair<int, int> w2, pair<int, int> w3) {
	for (int i = 1; i <= 8; i++)
		for (int j = 1; j <= 8; j++) c[i][j] = false;

	map[w1.first][w1.second] = 1;
	map[w2.first][w2.second] = 1;
	map[w3.first][w3.second] = 1;

	minVirus = min(minVirus, Bfs());

	map[w1.first][w1.second] = 0;
	map[w2.first][w2.second] = 0;
	map[w3.first][w3.second] = 0;

	return minVirus;
}
int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	int safety = 0;

	for(int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) {
				list.push_back(make_pair(i, j));
				safety++;
			}
			else if (map[i][j] == 2) virus.push(make_pair(i, j));
		}

	int answer;
	for(int i = 0; i < list.size()-2; i++)
		for(int j = i+1; j < list.size()-1; j++)
			for (int k = j + 1; k < list.size(); k++) {
				answer = WorkVirus(list[i], list[j], list[k]);
			}

	cout << safety - answer-3;
}

 

---

시행착오

브루트포스임을 알아차리는 것이 어려웠던 문제.

처음에는 브루트포스인 줄 모르고, 어려운 문제인 줄 알고 끙끙 앓다가
문제 조건을 다시 읽고 브루트포스임을 깨닫고는 구조를 짜는 것은 간단했다.

근데 생각보다 구현에는 시간이 오래 걸렸던 것 같다.
브루트포스 문제를 접하기에는 좋은 문제였던 것 같다.