백준 BOJ 14502 - 연구소

으으 소스가 너무 더러워...!

길이좀 줄여서 보기편하기 하는게 좋은데 소스가 너무 길어서 해독하기 힘들것 같다.

그래도 천천히 설명해보겠다...

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

14502번: 연구소

#include <stdio.h>

int n,m;
int arr[10][10];
int tmp[10][10];

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

void fill(int x, int y){
	tmp[x][y] = 2;
	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 && tmp[nx][ny] == 0){
			fill(nx,ny);
		}
	}
	return;
}

int f(int x1,int y1,int x2,int y2,int x3,int y3){
	tmp[x1][y1] = tmp[x2][y2] = tmp[x3][y3] = 1;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(tmp[i][j] == 2){
				fill(i,j);
			}
		}
	}
	int cnt=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(tmp[i][j] == 0) cnt++;
		}
	}
	return cnt;
}


int main(){
	int max = -1;
	int sum;
	scanf("%d %d", &n, &m);
	for(int i=0; i<n; i++) for(int j=0; j<m; j++) scanf("%d", &arr[i][j]);
	
	for(int x1=0; x1<n; x1++) for(int y1=0; y1<m; y1++){
		if(arr[x1][y1] != 0) continue;
		for(int x2=0; x2<n; x2++) for(int y2=0; y2<m; y2++){
			if(arr[x2][y2] != 0 || (x1==x2&&y1==y2)) continue;
			for(int x3=0; x3<n; x3++) for(int y3=0; y3<m; y3++){
				if(arr[x3][y3] != 0 || (x1==x3&&y1==y3) || (x3==x2&&y3==y2)) continue;
				for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp[i][j] = arr[i][j];
				sum = f(x1,y1,x2,y2,x3,y3);
				if(max < sum) max = sum;
			}
		}
	}
	printf("%d", max);
	return 0;
}

일단 메인함수부터보자면 안전영역의 최댓값을 반환해야 하므로 max값을 선언해준것을 알 수 있다.

넓이는 무조건 0 이상이니 max는 -1로 시작. sum은 그냥 임시변수.

​

입력받아야할 값들 전부 입력 받고,

완전 혼돈의 6중 포문이 나오는데 (한줄에 두개씩 겹쳐져있다)

이는 그냥 벽 세개를 새울 좌표를 일일히 전부 확인해본거라 확인하면 쉽다.

여기서 빈곳이 아닌 경우인데 벽을 세우는 경우나, 좌표가 같아 의미없는 경우들을 if문으로 제외해줬고,

f함수는 x1,y1, x2,y2, x3,y3 이 세개의 벽을 세웠을때의 안전영역의 크기를 구하는 함수이다.

 

int f(int x1,int y1,int x2,int y2,int x3,int y3){
	tmp[x1][y1] = tmp[x2][y2] = tmp[x3][y3] = 1;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(tmp[i][j] == 2){
				fill(i,j);
			}
		}
	}
	int cnt=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(tmp[i][j] == 0) cnt++;
		}
	}
	return cnt;
}

​

위 소스에서 f함수 부분만 잘라서 보자면

일단 벽을 전부다 세워줬고(1번줄)

이중포문을 돌려 바이러스가 발견되면 fill함수를 실행시키는데,

fill함수는 바이러스를 퍼트리는 함수이다.

​

바이러스를 모두 퍼트린 후 안전공간의 개수를 그 아래 포문에서 계산해서, 반환해주고 있는데

이게 어떻게 시간초과가 안나는지 계산을 해보면 좀 더 이해하기 쉬울 것 같다.

​

일단 8*8 크기에서 좌표 3개를 골라야 하므로

8*8*8*8*8*8 = 262144 만큼의 반복이 필요하고, f 함수 내에서 또 최대 64회의 반복이 필요하다.

최대한 간단히 중첩된 포문 수만 세어봤을때 대략 4천만번정도 반복하므로 충분히 시간내에 해결할수 있을거라는 감이 잡힐것이다.

​

이 문제는 참고로 proofed by AC 기법으로 증명되었으니 걱정하지 않아도 된다 ㅎㅎ

​