[백준] 14502: 연구소 (C++)
https://www.acmicpc.net/problem/14502
문제
문제의 연구소에 벽(1)을 최대 3개 설치가 가능하고 바이러스(2)는 벽이 막혀있는 곳 까지 퍼질 수 있다.
이러한 조건에서 바이러스가 퍼졌을 때, 안전한 장소(0)를 얼만큼 확보할 수 있는 지 출력하는 문제이다.
아이디어
BFS를 통해 바이러스를 퍼뜨린다.
벽을 최대 3개 설치할 수 있는 로직은 행열 순으로 벽을 하나씩 설치했다가 해제했다가 순서대로 모든 경우의 수를 구한다.
바이러스가 퍼진 상태 + 벽이 최대 3개가 설치된 상태에서 최대 안전한 장소가 얼마나 확보됐는지 비교하며 max값을 구한다.
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
예시의 원본으로 디버깅을 통한 예시를 들어본다.
2 1 1 1 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
2 1 1 0 1 1 1
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
2 1 1 0 1 1 0
1 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
2 1 1 0 1 1 0
0 1 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
2 1 1 0 1 1 0
0 0 1 1 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
,,,
2 1 1 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 1
2 1 0 1 1 1 1
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
2 1 0 1 1 1 0
1 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
...
이런식으로 벽을 세우는 모든 경우에서 바이러스를 BFS를 해주는 방식을 해주면 된다.
Code
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
// 상하좌우로 이동하기 위한 방향 배열
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int n, m; // 연구소의 크기 (세로, 가로)
int maxSafeArea = 0; // 최대 안전 영역의 크기
int lab[8][8]; // 연구소의 초기 상태
int originalLab[8][8]; // 벽을 세운 후의 임시 연구소 상태
void init(){
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
}
// 연구소 상태를 복사하는 함수
void copyLab(int (*dest)[8], int (*src)[8]) {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
dest[i][j] = src[i][j];
}
// BFS를 사용하여 바이러스를 퍼뜨리는 함수
void bfs() {
int spreadLab[8][8]; // 바이러스가 퍼진 후의 연구소 상태
copyLab(spreadLab, originalLab);
queue<pair<int, int>> q;
// 초기 바이러스 위치를 큐에 추가
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (spreadLab[i][j] == 2)
q.push(make_pair(i, j));
// BFS를 사용하여 바이러스를 퍼뜨림
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 범위 내에 있고 빈 칸인 경우 바이러스를 퍼뜨림
if (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (spreadLab[nx][ny] == 0) {
spreadLab[nx][ny] = 2;
q.push(make_pair(nx, ny));
}
}
}
}
// 오염되지 않은 안전 영역의 크기 계산
int safeArea = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (spreadLab[i][j] == 0)
safeArea++;
}
}
maxSafeArea = max(maxSafeArea, safeArea);
}
// 벽을 세우는 함수: 모든 벽을 세우는 경우를 구함.
void buildWall(int count) {
// 벽이 3개 세워졌을 때 바이러스를 퍼뜨림
if (count == 3) {
bfs();
return;
}
// 빈 칸에 벽을 세움
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (originalLab[i][j] == 0) {
originalLab[i][j] = 1;
buildWall(count + 1);
// 기존의 벽을 다시 빈 칸으로 돌려놓음
originalLab[i][j] = 0;
}
}
int main() {
init();
scanf("%d %d", &n, &m);
// 연구소의 초기 상태 입력
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &lab[i][j]);
// 모든 빈 칸에 대해 벽을 세우고 바이러스 퍼뜨림
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (lab[i][j] == 0) {
copyLab(originalLab, lab);
originalLab[i][j] = 1;
buildWall(1);
originalLab[i][j] = 0;
}
}
}
// 최대 안전 영역의 크기 출력
printf("%d\n", maxSafeArea);
}