백준 14502 연구소 C - Flood Fill, DFS

코로나 바이러스 시대에 알맞은 문제이다.

전체 N*M 크기의 방이 있으며 1은 벽, 2는 바이러스의 위치이다.

 

조건은 다음과 같다.

1. 바이러스는 벽이 없는 곳 상하좌우로 퍼질 수 있다.

2. 벽은 3개를 세워야한다.

3. 안전지대를 최대로 만들어야 한다.

 

접근 방식은 다음과 같다.

1. 맵의 크기가 최대 64로 작다.

2. 벽은 꼭 3개를 설치해야하며, 벽을 세울 수 있는 위치는 반드시 3개 이상 존재한다.

3. 바이러스는 최소 2개최대 10개까지이다.

 

벽을 놓을 수 있는 위치는 최대 62개이므로 (바이러스 2개, 벽 없을 때)

벽을 놓는 경우의 수는 62C3 이 될 것이고, 이것은 아주아주 작은 숫자(평소에 비하면)이므로 

총 연산은 62C3 * N^2 이므로 따로 최적화를 시도하지 않아도 충분히 풀 수 있을 것으로 기대된다.

 

해결 방식은 다음과 같다.

1. 벽을 놓을 장소를 3곳 고른다.(dfs)

2. 바이러스를 퍼뜨린다.(flood fill- dfs로 구현)

3. 안전지대의 크기를 계산하여 MAX보다 더 큰 경우 갱신한다.

4. 1~3을 반복하여 모든 경우의 수를 수행한다.

 

나는 0의 개수(벽을 놓을 수 있는 장소)를 미리 세어놓아 배열로 만들어 놓고, 바이러스도 배열로 만들어 놓았다. 

flood fill 을 진행하면서 퍼질 수 있는 장소의 개수를 세어 즉시 빈 방의 개수를 파악할 수 있다.

 

전체 코드

#include <stdio.h>
#include <string.h>
#define MAX_N 8
#define MAX_M 8
int N, M;
int idx_zero, idx_virus; //0의 개수, 바이러스의 개수

int Map[MAX_N][MAX_M];//인풋
int visited[MAX_N][MAX_M];//flood fill 기록
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int ans;//최종 답
int cnt;//바이러스 퍼지는 방의 수

typedef struct st {
	int y, x;
}CO;
CO empty[MAX_N * MAX_N]; //0이 있는 곳의 좌표
int used[MAX_N*MAX_N]; //0 좌표 선택 여부 
CO virus[10];//바이러스 좌표

int floodfill(int y, int x) {

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
		if (visited[ny][nx]) continue;
		//0인 곳만 퍼질 수 있음
		if (Map[ny][nx]) continue;
		visited[ny][nx] = 1;
		//퍼진 횟수 기록
		cnt++;
		floodfill(ny, nx);
	}
	return 0;
}


int select(int idx, int num) {
	//벽 놓을 위치 3곳 다 선택했을 경우
	if (num == 3) {
		//초기화
		cnt = 0;
		memset(visited, 0, sizeof(visited));
		//바이러스 별로 flood fill 진행
		for (int i = 0; i < idx_virus; i++) {
			floodfill(virus[i].y, virus[i].x);
		}
		//최대값보다 큰 값이 나올 때 저장
		if (ans < idx_zero - cnt-3) {
			// -3은 벽을 놓은 세 곳 제외한 것
			ans = idx_zero - cnt - 3;
		}
		return 0;
	}
	//중복 제거를 위해 i= idx부터 시작
	for (int i = idx; i < idx_zero; i++) {
		if (used[i]) continue;
		used[i] = 1;
		Map[empty[i].y][empty[i].x] = 1;
		select(i, num + 1);
		used[i] = 0;
		Map[empty[i].y][empty[i].x] = 0;
	}
	return 0;
}

int solve() {
	select(0, 0);

	return 0;
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &Map[i][j]);
			if (Map[i][j] == 0) {
				empty[idx_zero].y = i;
				empty[idx_zero++].x = j;
			}
			else if (Map[i][j] == 2) {
				virus[idx_virus].y = i;
				virus[idx_virus++].x = j;
			}
		}
	}
	solve();
	printf("%d", ans);
}