백준 14502번
오늘 풀어본 문제는 백준의 14502번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 $N \times M$ 인 직사각형으로 나타낼 수 있으며, 직사각형은 $1 \times 1$ 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 $3$ 개이며, 꼭 $3$ 개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
이때, $0$ 은 빈 칸, $1$ 은 벽, $2$ 는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
$2$ 행 $1$ 열, $1$ 행 $2$ 열, $4$ 행 $6$ 열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
벽을 $3$ 개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 $27$ 이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 $N$ 과 가로 크기 $M$ 이 주어진다. $(3 \le N, M \le 8)$
둘째 줄부터 $N$ 개의 줄에 지도의 모양이 주어진다. $0$ 은 빈 칸, $1$ 은 벽, $2$ 는 바이러스가 있는 위치이다. $2$ 의 개수는 $2$ 보다 크거나 같고, $10$ 보다 작거나 같은 자연수이다.
빈 칸의 개수는 $3$ 개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
풀이과정
1번째 시도
문제를 처음보고 벽을 설마 일일히 다 세워보고 BFS를 돌려야 하나 싶었는데, $N$ 과 $M$ 의 크기를 보고 가능할 것 같아 그대로 풀기로 하였다.
우선 어떤 실험실의 상태를 받아 BFS를 돌려 안전구역의 개수를 세는 함수를 만든 뒤, 빈 공간 $3$ 개를 골라 벽을 세울 수 있는 모든 조합을 시도하면서 해당 함수를 호출하고, 안전 구역의 개수의 최댓값을 알아내어 출력하는 방식으로 문제 해결을 시도하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int N, M;
int lab[8][8] = {0,};
int newLab[8][8] = {0,};
vector<pair<int, int>> initVirus;
vector<pair<int, int>> emptySpace;
void deepCopy(void);
int getSafeZoneArea(void);
bool isInRange(pair<int, int> pos);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int result = 0;
cin >> N >> M;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
int info;
cin >> info;
if (info == 0) {
emptySpace.emplace_back(i, j);
}
else if (info == 2) {
initVirus.emplace_back(i, j);
}
lab[i][j] = info;
}
}
for (int i=0; i<emptySpace.size()-2; i++) {
for (int j=i+1; j<emptySpace.size()-1; j++) {
for (int k=j+1; k<emptySpace.size(); k++) {
deepCopy();
newLab[emptySpace[i].first][emptySpace[i].second] = 1;
newLab[emptySpace[j].first][emptySpace[j].second] = 1;
newLab[emptySpace[k].first][emptySpace[k].second] = 1;
result = max(result, getSafeZoneArea());
}
}
}
cout << result;
return 0;
}
void deepCopy(void) {
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
newLab[i][j] = lab[i][j];
}
}
}
int getSafeZoneArea(void) {
int area = 0;
queue<pair<int, int>> q;
for (auto& i: initVirus) {
q.push(i);
}
while (!q.empty()) {
pair<int, int> curr = q.front();
q.pop();
for (int i=0; i<4; i++) {
pair<int, int> newPos = make_pair(curr.first + dx[i], curr.second + dy[i]);
if (isInRange(newPos) && newLab[newPos.first][newPos.second] == 0) {
newLab[newPos.first][newPos.second] = 2;
q.push(newPos);
}
}
}
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (newLab[i][j] == 0) {
area++;
}
}
}
return area;
}
bool isInRange(pair<int, int> pos) {
if (pos.first < 0 || pos.first > N - 1) {
return false;
}
else if (pos.second < 0 || pos.second > M - 1) {
return false;
}
else {
return true;
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
간만에 브루트포스 문제가 나와 반가웠다. 강력한 컴퓨팅 파워로 밀어붙여서 문제를 해결한다는게 뭔가 멋있고 웃기게 들리지 않는가? 아님 말고…
오늘 문제를 풀면서 이제 CLASS 4 MASTER에 도달하기까지 단 2개의 문제만이 남았다. 내일과 내일 모레에 문제를 제 때 풀어낸다면, 정확히 새해 1월 1일에 CLASS 4 MASTER 를 달성하게 되는 것이다! 감기 때문에 쉬지만 않았어도 4 대신 5나 6일 수도 있었는데 조금 아쉽긴 한다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/14502