[백준] 14502번: 연구소

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

14502번: 연구소

 

문제 이해

저번에 봤던 연구소3이랑 비슷하다.

근데 이번에는 3개의 벽을 세우는 것이다.

 

3개의 벽을 세울 곳을 지정한 후에, 그 상황에서 바이러스가 퍼지는 것을 구현하고, 바이러스가 퍼지지 않은 빈칸의 개수를 세면 된다.

 

벽 세울 3곳을 구하기 위해서 처음에 입력받을 때 빈 칸의 좌표들을 blank라는 배열에 저장해줬다. 

바이러스 퍼지는 것 구현할 때 바이러스를 빨리 enqueue하기 위해서 virus라는 배열에 virus 초기 위치 좌표들도 저장해두었다.

 

1. 벽 세울 곳 정하기 ( DFS() )

DFS를 통해 벽 세울 3군데를 정하면 된다. blank배열에 빈 칸들 있으니까 이 중에서 3개를 구하면 되고, 순서는 상관없으니까 조합이다. 

void DFS(int cnt, int idx) {

	// 종료
	if (cnt == 3) {
		int res = BFS();
		if (res > max) max = res;
		return;
	}

	// 재귀
	for (int i = idx; i < bcnt; i++) {
		int y = blank[i].y;
		int x = blank[i].x;
		map[y][x] = 1; 
		DFS(cnt + 1, i + 1);
		map[y][x] = 0;
	}

}

 

2. 바이러스 퍼뜨리기 ( BFS() )

visited 배열에 벽까지 세운 map 상태를 memcpy해 둔 다음에 BFS를 돌렸다.

b라는 변수에 빈칸 개수 - 3 (벽 세웠으니까) 를 저장해두고, 바이러스가 퍼지면서 빈 칸이 차게되면 이 b를 하나씩 줄여서 마지막에 남은 빈 칸 수를 바로 return할 수 있도록 했다.

int BFS(void) {
	wp = rp = 0;
	int b = bcnt - 3;
	memcpy(visited, map, sizeof(map));
	for (int i = 0; i < vcnt; i++) {
		enq(virus[i].y, virus[i].x);
		//visited[virus[i].y][virus[i].x] = 2;
	}
	while (!empty()) {
		POS cur = deq();
		for (int i = 0; i < 4; i++) {
			int ny = dy[i] + cur.y;
			int nx = dx[i] + cur.x;
			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (visited[ny][nx] == 2) continue;
			if (map[ny][nx] == 1) continue; // 벽
			enq(ny, nx);
			visited[ny][nx] = 2;
			b--;
		}
	}

	return b;
}

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXMN 8

int N, M;
int map[MAXMN + 1][MAXMN+1];
int visited[MAXMN + 1][MAXMN+1];
typedef struct st {
	int y, x;
}POS;
POS blank[MAXMN * MAXMN];
int bcnt;
POS virus[MAXMN * MAXMN];
int vcnt;
int max;

POS q[MAXMN * MAXMN * 10];
int wp, rp;
void enq(int y, int x) { q[wp].y = y, q[wp++].x = x; }
POS deq(void) { return q[rp++]; }
int empty(void) { return wp == rp; }

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

void Get_Input(void) {
	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) {
				blank[bcnt].y = i, blank[bcnt++].x = j;
			}
			if (map[i][j] == 2) {
				virus[vcnt].y = i, virus[vcnt++].x = j;
			}
		}
	}
}


int BFS(void) {
	wp = rp = 0;
	int b = bcnt - 3;
	memcpy(visited, map, sizeof(map));
	for (int i = 0; i < vcnt; i++) {
		enq(virus[i].y, virus[i].x);
		//visited[virus[i].y][virus[i].x] = 2;
	}
	while (!empty()) {
		POS cur = deq();
		for (int i = 0; i < 4; i++) {
			int ny = dy[i] + cur.y;
			int nx = dx[i] + cur.x;
			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (visited[ny][nx] == 2) continue;
			if (map[ny][nx] == 1) continue; // 벽
			enq(ny, nx);
			visited[ny][nx] = 2;
			b--;
		}
	}

	return b;
}



void DFS(int cnt, int idx) {

	// 종료
	if (cnt == 3) {
		int res = BFS();
		if (res > max) max = res;
		return;
	}

	// 재귀
	for (int i = idx; i < bcnt; i++) {
		int y = blank[i].y;
		int x = blank[i].x;
		map[y][x] = 1; 
		DFS(cnt + 1, i + 1);
		map[y][x] = 0;
	}

}

int main(void) {
	Get_Input();
	DFS(0, 0);
	printf("%d", max);
	return 0;
}