백준 14502번 - 연구소

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

14502번: 연구소

풀이 과정

 연구소 임의 위치에 3개의 벽을 설치하면서, 바이러스가 최소로 퍼지는, 안전 영역의 최댓값을 구하는 문제이다.

 

 for문을 이용해 연구소에 3개의 벽을 설치하는 모든 경우의 수를 탐색한다. 상태를 초기화하고, 바이러스를 전파 그리고 안전 영역 크기를 구하며 최댓값을 갱신해준다. 바이러스를 전파할 때는 DFS를 사용했다.

 

느낀점

 완전 탐색으로 모든 경우의 수를 탐색하며 풀었다. 위 풀이 과정을 사전에 머릿 속에 그리고 하니 수월하게 풀린 것 같다.

 

 

#include<bits/stdc++.h>
using namespace std;

const int MAX = 8;
int n, m, cnt, ret;
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
int mp[MAX][MAX], visited[MAX][MAX], mp_temp[MAX][MAX];
vector<pair<int, int>> space;

//바이러스 전이 DFS
void DFS(int y, int x) {
	if (visited[y][x] || mp[y][x] == 1) return;
	visited[y][x] = 1;
	mp_temp[y][x] = 2; //전이
	for (int d = 0; d < 4; d++) {
		int ny = my[d] + y;
		int nx = mx[d] + x;
		if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		DFS(ny, nx);
	}
	return;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mp[i][j];
			if (!mp[i][j]) space.push_back({ i, j });
		}
	}

	for (int i = 0; i < space.size() - 2; i++) {
		for (int j = i + 1; j < space.size() - 1; j++) {
			for (int k = j + 1; k < space.size(); k++) {\
				//벽 세우기
				mp[space[i].first][space[i].second] = 1;
				mp[space[j].first][space[j].second] = 1;
				mp[space[k].first][space[k].second] = 1;
                
				//바이러스 전이 전 상태 불러오기 및 visited 초기화
				copy(&mp[0][0], &mp[0][0] + MAX * MAX, &mp_temp[0][0]);
				fill(&visited[0][0], &visited[0][0] + MAX * MAX, 0);

				//바이러스 뿌리기
				for (int vi = 0; vi < n; vi++) {
					for (int vj = 0; vj < m; vj++) {
						if(mp_temp[vi][vj] == 2) DFS(vi, vj);
					}
				}
		
				//안전 영역 카운트
				cnt = 0;
				for (int si = 0; si < n; si++) {
					for (int sj = 0; sj < m; sj++) {
						if (mp_temp[si][sj] == 0) cnt++;
					}
				}

				//최댓값 갱신
				ret = max(cnt, ret);

				//벽 철거
				mp[space[i].first][space[i].second] = 0;
				mp[space[j].first][space[j].second] = 0;
				mp[space[k].first][space[k].second] = 0;
			}
		}
	}

	cout << ret;

	return 0;
}