[BAEKJOON] 14502번 연구소

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

14502번: 연구소

문제조건

1. 벽(1)을 무조건 3개를 세운다.
2. 벽은 바이러스(2)가 퍼져 나가는걸 막아준다.
3. 안전영역(0)의 크기가 최댓값은 얼마인가?

접근방법

 

애초에 입력이 8이하로 너무 작아서 진짜 내 맘대로 구현할 수 있는 문제였다.

처음에는 최대한 깔끔하게 로직을 짤 수 없을까란 생각이 계속 들었지만, 그리디도 아니고, 어느 알고리즘도 적용할 수 없었다. 여기에 시간을 좀 많이 쏟은것 같다.

단순하게 문제조건만 맞춘다면 어려울 것 없는 문제다.

안전영역의 크기가 최대가 되기 위해서는 바이러스가 퍼지는 영역이 최소가 되면 된다에 집중해서 풀이했다.

1.  Brute Force로 벽 3개를 세워서 모든 경우의 수를 생각해줬다.
2. 각 경우의 수마다 BFS를 바이러스(2)기준으로 수행해서 바이러스가 퍼진 수를 체크하고, 최솟값을 갱신했다.
3. 물론, 각 경우의 수를 생각해주기 위해 map을 임시로 1로 바꿔줬다가 한번의 경우가 끝나면 0으로 다시 복구시켰다.
4. 모든 경우를 탐색하고 최소 바이러스수가 나오면 전체 맵에서 0의 개수를 구한다.

0의개수 : 전체맵(n x m) - 벽(1)의 개수 - 최소 바이러스 수

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int n, m, map[9][9], visited[9][9];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };
int one;
vector<pair<int, int> > v;
vector<pair<int, int> > virus;

//바이러스 퍼져나감
int bfs(int y, int x) {
	int sum = 1;
	queue<pair<int, int> > q;
	q.push({ y,x });
	visited[y][x] = 1;
	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if (map[ny][nx] != 1 && !visited[ny][nx]) {
				visited[ny][nx] = 1;
				sum++;
				q.push({ ny,nx });
			}
		}
	}
	return sum;
}

// 0의 개수 세기
int main(){
	cin >> n >> m;
	int res = 100;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (!map[i][j]) v.push_back({ i,j });
			else if (map[i][j] == 2) virus.push_back({ i,j });
			else if (map[i][j] == 1) one++;
		}
	}
	//벽 3개 세우기
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < i; j++) {
			for (int k = 0; k < j; k++) {
				int cnt = 0;
				map[v[i].first][v[i].second] = map[v[j].first][v[j].second] = map[v[k].first][v[k].second] = 1;
				for (int spread = 0; spread < virus.size(); spread++) {
					if(!visited[virus[spread].first][virus[spread].second])
						cnt += bfs(virus[spread].first, virus[spread].second);
				}
				res = min(res, cnt);
				memset(visited, 0, sizeof(visited));
				map[v[i].first][v[i].second] = map[v[j].first][v[j].second] = map[v[k].first][v[k].second] = 0;
			}
		}
	}
	cout << n*m - (one+3) - res;
}

 

for문 중첩이 엄청 심한데 어디까지나 이 문제의 입력이 엄청나게 작다는 걸 생각하고, 좀 더 좋은 로직을 짜도록 노력하자,,!! 근데 이번 문제는 전체 탐색을 어떻게 하지라는 부분을 가장 많이 고민했다,,,