이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14502번 문제 '연구소'의 풀이 코드와 해설을 다룹니다. (Solved.ac 기준 난이도 Gold V)
14502번 : 연구소
세로 크기 N, 가로 크기 M인 연구소 지도가 주어지고 0은 빈 공간, 1은 벽, 2는 바이러스라고 할 때 벽 3개를 세워 얻을 수 있는 안전 영역의 최대 크기를 출력하는 문제입니다.
눈에 띄는 것은 입력 범위인데, 지도의 크기는 아무리 커도 가로, 세로 8칸이 넘지 않으므로 최대 64칸의 면적이 최대입니다.
이 경우 벽을 세울 3칸을 선택할 수 있는 경우의 수는 아무리 많아도 64C3 = (64*63*62)/(3*2*1) = 41664가지를 넘지 않습니다.
그리고 각각의 경우에 대해 BFS를 수행하더라도 연산의 횟수가 많지 않습니다.
따라서 이 문제는 완전 탐색에 해당하는 브루트포스 알고리즘으로 해결할 수 있습니다.
#include<stdio.h>
int N, M, next_x, next_y, max = 0;
int map[10][10] = {0, }, map_copy[10][10] = {0, }, move_dir[2][4] = {{1, -1, 0, 0}, {0, 0, 1, -1}};
struct node { int x, y; };
void BFS() {
struct node queue[100];
int front = 0, rear = 1, count = 0;
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++) {
map_copy[i][j] = map[i][j];
if(map_copy[i][j] == 2) queue[rear].x = j, queue[rear++].y = i;
}
while(++front < rear) {
for(int i=0; i<4; i++) {
next_x = queue[front].x + move_dir[0][i];
next_y = queue[front].y + move_dir[1][i];
if(next_x >= 1 && next_x <= M && next_y >= 1 && next_y <= N && !map_copy[next_y][next_x]) {
map_copy[next_y][next_x] = 2;
queue[rear].x = next_x;
queue[rear++].y = next_y;
}
}
}
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++)
if(!map_copy[i][j]) count++;
if(count > max) {
max = count;
/*printf("\n");
for(int i=1; i<=N; i++) {
for(int j=1; j<=M; j++) printf("%d ", map_copy[i][j]);
printf("\n");
}*/
}
}
void wall_select(int wall_count) {
if(wall_count == 3) {
BFS();
return;
}
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++)
if(!map[i][j]) {
map[i][j] = 1;
wall_select(wall_count + 1);
map[i][j] = 0;
}
}
int main() {
scanf("%d %d", &N, &M);
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++) scanf("%d", &map[i][j]);
wall_select(0);
printf("%d", max);
}
3개 벽의 설정을 단순 반복문으로 설정하기에는 다수의 변수가 필요하기 때문에 wall_select 함수를 재귀함수로 설정하여 벽을 세팅하도록 구현하였습니다.
재귀함수로 구현하였을 때 좋은 점은 벽을 설정하고 해당 반복문이 끝나면 다시 벽을 없애고 다른 벽을 설정하는 백트래킹 구조의 구현이 아주 용이하다는 것입니다.
벽을 모두 설정한 이후에는 각 경우에 대해 BFS를 수행하여 바이러스를 전염시킨 뒤, 남아있는 공간의 수를 세는 과정을 거쳤습니다.
BFS는 큐를 이용하여 구현하되 move_dir 배열을 사용하여 상하좌우 블럭을 검사 시 코드가 반복되는 것을 줄였습니다.
남아있는 공간의 수가 기존 max 값보다 크면 max 값을 갈아치우고, 모든 벽의 설정에 대해 검사가 끝난 이후 마지막에 max 값을 출력하도록 코드를 작성하였습니다.
주석 부분은 max 값이 갱신될 때마다 해당 벽의 위치와 감염 후 연구실의 상태를 출력하는 함수입니다.
풀이 코드를 제출하기 전에 답안의 이해를 위해서 주석 부분을 지우고 확인해보시면 좋습니다.
제가 위와 같은 예제를 대입하여 최대한 공간을 확보하는 벽의 설정이 어떻게 되는지 확인해보겠습니다.
출력부 코드는 정밀하게 작성하지 않아 max 값이 갱신될 때마다 출력되기 때문에, 마지막 출력만 봐주시면 됩니다.
위와 같이 벽을 통해 두 군데로 나누어 최대 공간을 확보하는 것을 확인할 수 있습니다.