[백준] 17142번: 연구소 3

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

17142번: 연구소 3

 

문제 이해

푸는 방식도 쉽게 생각해낼 수 있고, 심지어 그냥 지나칠 수 있는 여러 예외 케이스들을 예제로 줘서 문제 푸는데 어려움이 없는 문제였다. 

• 예제 6과 같이, 어떻게 선택하든 모든 빈 칸에 바이러스를 채우지 못하는 경우
• 예제 7과 같이, 처음부터 모든 칸에 바이러스가 있는 경우

를 고려해야 한다. 

 

결론부터 말하자면 vcnt개의 바이러스 중에 M개를 선택(DFS)해서 이 M개 바이러스 위치에서 모든 맵에 확산하는 최소한의 시간을 (혹은 최단 경로)를 구하면 된다.(BFS)

 

처음에 헷갈렸던 게 M개의 바이러스가 들어오는 줄 알았다. 그게 아니라, 몇 개의 바이러스가 들어오는지는 정수로 주지 않고 맵을 받으면서 세야 한다.

 

1. vcnt 개의 바이러스 중에서 M개의 바이러스를 선택한다. 이때 DFS를 이용한다.

void DFS(int cnt, int idx) {
	// 종료
	if (cnt == M) {
		int res = BFS();
		if (res == -1) return;
		if (res < min_time) min_time = res;
		return;
	}

	// 재귀
	for (int i = idx+1; i < vcnt; i++) {
		sel[cnt] = i;
		DFS(cnt + 1, i);
	}
}

2. M개의 바이러스를 선택하고 나면 그 바이러스들로부터 BFS를 수행한다.

이때 주의할 점은 바이러스가 이미 있는 칸은 방문을 안해도 되기 때문에 처음에 맵을 받을 때 blank라는 변수에 빈 칸의 개수를 저장했다가, 빈칸에 바이러스를 채울 때마다 blank의 카피본인 b를 감소시켰다. 그리고 b가 0이 되는 순간에 그때까지의 시간을 리턴한다. 

int BFS(void) {
	wp = rp = 0;
	memset(visited, 0, sizeof(visited));
	int b = blank;

	for (int k = 0; k < M; k++) {
		int i = sel[k];
		enq(v[i].y, v[i].x, 0);
		visited[v[i].y][v[i].x] = 1;
	}

	while (!empty()) {
		ELE cur = deq();
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (visited[ny][nx] != 0) continue;
			if (map[ny][nx] == 1) continue;
			enq(ny, nx, cur.time + 1);
			visited[ny][nx] = cur.time + 1;
			if (map[ny][nx] == 0) b--;
			if (b == 0) {
				return cur.time + 1;
			}
		}
	}

	return -1;
}

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 50
#define MAXM 10

int N, M;
int map[MAXN + 5][MAXN + 5];
int visited[MAXN + 5][MAXN + 5];
typedef struct st {
	int y, x;
}VIRUS;
VIRUS v[MAXM + 5];
int sel[MAXM + 5];
int vcnt;
int blank;
int min_time = 0x7fffffff;

void Get_Input(void) {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for(int j = 0; j<N; j++){
			scanf("%d", &map[i][j]); 
			if (map[i][j] == 2) {
				// virus임
				v[vcnt].y = i, v[vcnt++].x = j;
			}
			if (map[i][j] == 0) blank++;
		}
	}
}

typedef struct st2 {
	int y, x, time;
}ELE;
ELE q[MAXN * MAXN * 10];
int wp, rp;
void enq(int y, int x, int time) {
	q[wp].y = y, q[wp].x = x, q[wp++].time = time;
}
ELE deq() { return q[rp++]; }
int empty() { return rp == wp; }

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

int BFS(void) {
	wp = rp = 0;
	memset(visited, 0, sizeof(visited));
	int b = blank;

	for (int k = 0; k < M; k++) {
		int i = sel[k];
		enq(v[i].y, v[i].x, 0);
		visited[v[i].y][v[i].x] = 1;
	}

	while (!empty()) {
		ELE cur = deq();
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (visited[ny][nx] != 0) continue;
			if (map[ny][nx] == 1) continue;
			enq(ny, nx, cur.time + 1);
			visited[ny][nx] = cur.time + 1;
			if (map[ny][nx] == 0) b--;
			if (b == 0) {
				return cur.time + 1;
			}
		}
	}

	return -1;
}

void DFS(int cnt, int idx) {
	// 종료
	if (cnt == M) {
		int res = BFS();
		if (res == -1) return;
		if (res < min_time) min_time = res;
		return;
	}

	// 재귀
	for (int i = idx+1; i < vcnt; i++) {
		sel[cnt] = i;
		DFS(cnt + 1, i);
	}
}

void Solve(void) {
	// vcnt 개의 바이러스 중 M개를 선택한다
	DFS(0, 0);
}

int main(void) {
	freopen("in.txt", "r", stdin);
	Get_Input();
	if(blank != 0){
		DFS(0, -1);
		if (min_time == 0x7fffffff) printf("-1");
		else printf("%d", min_time);
	}
	else {
		printf("0");
	}
	return 0;
}