[백준 14502] 연구소 cpp

문제
연구의 크기가 NxM일 때 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 
바이러스가 퍼지는 것을 막기위해 벽은 3개를 세울 수 있다. 3개의 벽을 세운 뒤에 바이러스가 퍼질 수 없는 곳을 안전영역이라 하는데 안전영역 크기의 최댓값을 구하라.

입력
첫째 줄에 지도의 크기인 N, M 입력 3이상 8이하
둘째 줄부터 지도의 모양을 입력하며 바이러스인 2의 개수는 2이상 10이하이다. 빈 칸의 개수는 3개 이상

출력
안전영역의 최댓값을 출력

---

문제에서 반드시 3개의 벽을 세워야한다고 했다. 여기서 다음 두 가지를 구현하면된다.

1. 벽을 세우는 로직

2. 벽을 세운 후에 바이러스를 퍼트리는 로직

 

먼저 벽을 세우는 로직을 어떻게 구현하면 좋을지 생각해보자.

맵에서 0은 빈 칸이고 벽을 세울 수 있는 공간이다. 따라서 0에 해당되는 모든 칸에 대하여 벽을 세우면 될 것이다. 이때 시간복잡도를 계산해보자.

 

최대 8x8의 칸(64칸)에서 바이러스는 최소 2칸, 벽은 0칸이므로 62칸이 빈 칸이 될 수 있다. 여기서 벽을 세우는 경우의 수는 62x61x60 = 226,920이 된다. 이에 더하여 벽을 세운 후에 맵을 검색하면서 바이러스를 퍼트리기 때문에 대략 13,000,000이하가 될 것이다. (틀린 계산이라면 댓글로 지적부탁드립니다.)

 

따라서 모든 빈 칸에 대하여 3개의 벽을 세워보면 될것이다. 그렇다면 어떻게 벽을 세울 것인가?라고 했을 때 문제에서 말하는 연구소 지도를 어떻게 모델링할 것인지 생각해본다. 이 문제에서는 2차원 배열을 사용하기로 하고 빈 칸은 0, 벽은 1, 바이러스는 2로 표시한다. 맵에 대한 정보를 입력받고 맵을 탐색해본다.

 

맵 탐색 중 0이 나온다면 벽을 세우고 벽을 세우는 함수인 SetWall()이 실행되도록 한다. 이 함수에서는 3개의 벽을 세우고 3개의 벽을 세웠다면 바이러스를 퍼트리는 기능을 한다. 벽을 세우고 SetWall()가 실행되고 빠져나왔을 때 다시 해당 좌표에 0을 대입하여 빈 칸으로 해준다. (백트래킹)

 

그 다음 바이러스를 퍼트리는 로직을 구현해보자.

BFS를 통해 먼저 바이러스 주변으로 점점 퍼져나가도록 한다. 벽을 세운 맵을 복사하고 바이러스의 좌표를 큐에 담는다. 이후 BFS를 진행하여 상하좌우에 빈 칸이고 맵을 벗어나지 않는다면 바이러스를 퍼트린다.

 

바이러스를 모두 퍼트린 후에 빈 칸을 카운트하여 안전영역을 구하고 최종해와 비교하여 최댓값을 갱신하도록 한다.

#include "pch.h"
#include <iostream>
#include<algorithm>
#include<queue>
using namespace std;

int map[8][8];
int answer;
int N, M;
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

bool Range(int y, int x) {
	return(y >= 0 && y < N) && (x >= 0 && x < M);
}


void BFS() {
	int copy_map[8][8] = { 0, };
	queue<pair<int, int>> q;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			copy_map[i][j] = map[i][j];
			if (map[i][j] == 2)
				q.push({ i,j });
		}
	}

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int dy = y + dir[d][0];
			int dx = x + dir[d][1];
			if (Range(dy, dx) && copy_map[dy][dx] == 0) {
				copy_map[dy][dx] = 2;
				q.push({ dy,dx });
			}
		}
	}

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (copy_map[i][j] == 0)
				cnt++;
		}
	}

	answer = max(answer, cnt);
	return;
}
void SetWall(int wall) {
	if (wall == 3) {
		BFS();
		return;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				SetWall(wall + 1);
				map[i][j] = 0;
			}
		}
	}
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				SetWall(1);
				map[i][j] = 0;
			}
		}
	}
	cout << answer << endl;
	return 0;
}

 

느낀점

알고리즘 문제를 이해하고 가장 먼저 어떻게 접근하면 좋을지 생각해보고 풀이방법이 떠올랐다면 어떤 기능을 구현해야하는지 정리하고 문제에서 주어진 것을 어떻게 모델링할지 생각해보도록 한다.