#문제
14502번: 연구소
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
#접근방법
이 문제는 지도의 크기가 최대 8*8 = 64칸이 최대이므로 모든 경우의 수를 구해도 64*63*62*dfs가 걸리는 시간이므로 시간안에 돌아간다. 벽 3개를 설치하는 모든 경우의 수에서 dfs를 돌려서 안전영역이 최대가 되는 경우를 계산해주면 된다.
#풀이
#include <stdio.h>
int arr[10][10];
int arr2[10][10];
int virus[64][2];
int num;
int n,m;
int xx[4]={0,0,-1,1};
int yy[4]={1,-1,0,0};
void dfs(int x, int y){
for(int i=0;i<4;i++){
int X = x+xx[i];
int Y = y+yy[i];
if(X>0 && X<=n && Y>0 && Y<=m && !arr2[X][Y]){
arr2[X][Y] = 2;
dfs(X,Y);
}
}
return;
}
int main(){
int x1,x2,x3,y1,y2,y3;
int ans = 0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&arr[i][j]);
arr2[i][j] = arr[i][j];
if(arr[i][j]==2){
virus[num][0] = i;
virus[num][1] = j;
num++;
}
}
for(int i=0;i<n*m;i++){
x1=i/m+1; y1=i%m+1;
if(!arr2[x1][y1])
for(int j=i+1;j<n*m;j++){
x2=j/m+1; y2=j%m+1;
if(!arr2[x2][y2])
for(int k=j+1;k<n*m;k++){
x3=k/m+1; y3=k%m+1;
if(!arr2[x3][y3]){
arr2[x1][y1] = 1;
arr2[x2][y2] = 1;
arr2[x3][y3] = 1;
for(int p=0;p<num;p++)
dfs(virus[p][0],virus[p][1]);
int cnt = 0;
for(int p=1;p<=n;p++)
for(int q=1;q<=m;q++)
if(!arr2[p][q]) cnt++;
if(ans<cnt)
ans = cnt;
for(int p=1;p<=n;p++)
for(int q=1;q<=m;q++)
arr2[p][q] = arr[p][q];
}
}
}
}
printf("%d",ans);
return 0;
}
n,m을 입력받고 arr배열과 arr2배열에 연구소 모양을 저장시켜준다. arr2배열은 벽 3개를 설치하고 바이러스를 퍼뜨리는 시뮬레이션을 하는 배열이다. 그리고 virus배열에 바이러스의 좌표를 저장해준다.
벽 3개를 설치하는 모든 경우의 수를 구하기 위해서 0 ~ n*m-1까지 반복하는 반복문 3개를 만들어 주었고,
(x1,y1), (x2,y2), (x3,y3)는 각각 벽 3개의 좌표들이다. 각각의 좌표를 구할 때, x1 = i/m+1; y1 = i%m+1으로 적절한 연산을 통하여 계산해주었고, 그 좌표에 0이 들어있을 때 벽을 설치해주는 조건문을 넣어주었다.
벽 3개의 좌표를 구했으면 해당 좌표 칸에 1을 넣어주고, 바이러스의 개수 만큼 반복문을 돌려서 dfs를 실행시켜 주면 해당 경우의 수에 안전지대가 몇 개인지 개수가 나온다. 하나의 시뮬레이션을 끝내면 arr2배열을 arr로 다시 초기화 시켜주어서 다시 반복을 해주면 된다.
모든 경우의 수에서 안전지대의 최대값을 구해주면 정답이다.
#성능
#정리
모든 경우의 수를 구하기 위해 3개의 반복문과 dfs를 돌리면 된다는 것,
적절한 연산, 조건문과 이를 구현할 수 있는 능력이 있으면 풀 수 있는 문제였다.
'하루 한 문제' 카테고리의 다른 글
[백준] 17070번 : 파이프 옮기기 1 [C/C++] (0) | 2022.01.18 |
---|---|
[백준] 15686번 : 치킨 배달 [C/C++] (0) | 2022.01.18 |
[백준] 13549번 : 숨바꼭질 3 [C/C++] (2) | 2022.01.15 |
[백준] 13172번 : Σ [C/C++] (0) | 2022.01.15 |
[백준] 12865번 : 평범한 배낭 [C/C++] (0) | 2022.01.12 |