[백준] 14502번 : 연구소 [C/C++]

#문제

14502번: 연구소

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

14502번: 연구소

 

---

#접근방법

이 문제는 지도의 크기가 최대 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를 돌리면 된다는 것,

 

적절한 연산, 조건문과 이를 구현할 수 있는 능력이 있으면 풀 수 있는 문제였다.