[BOJ-17142] 연구소3

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

 

문제 풀이 시간 : 2시간

 

예제 케이스를 디버깅하다가 비활성 바이러스를 활성 바이러스로 바꿔줬을 때 소요시간 처리하는 것에서 잘못된 값이 들어가는 것을 확인하고 이것을 수정해주느라 시간이 많이 걸렸다. 실제 시험장에서 긴장했을 경우, 실수했을때 소요되는 시간을 고려해본다면 아마 3시간 동안 한 문제를 간신히 풀었을 것으로 생각된다..

 

내가 생각하는 문제의 요점은 바이러스를 퍼뜨리는데 소요되는 시간을 정확히 구해야 한다.

(비활성 바이러스를 활성화 바이러스로 바꾸는 것은 바이러스를 퍼뜨리는 것이 아님)

 

-----------------------------------------------------------------------------------------------------------------------------------

 

- 문제 풀이

 

1. 바이러스 위치 정보를 입력 받는다.

2. 입력 받을 때, 바이러스의 좌표만 따로 vector에 저장한다.

3. dfs로 저장한 바이러스의 좌표를 m개씩 선택하고 이 바이러스들을 활성화 바이러스로 바꿔준다.

4. bfs로 바이러스를 퍼뜨리고 시간 정보를 기록한다.

5. map에 기록된 정보와 visited에 기록된 정보를 이용해 바이러스가 다 퍼졌는지 유무를 검사한다.

6. 다 퍼지지 않았을 경우 -1을 출력하도록 하고 아닐 경우 소요된 시간을 출력한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>

using namespace std;

struct VIRUS {
	int y, x, time;
};
int n, m, res;
int map[50][50];
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
vector<VIRUS> vec, sel;

void dfs(int node) {

	if (sel.size() == m) {

		queue<VIRUS> q;
		int visited[50][50];

		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				visited[y][x] = -1;
			}
		}
		for (int i = 0; i < sel.size(); i++) {
			q.push(sel[i]);
			visited[sel[i].y][sel[i].x] = 0;
		}

		while (!q.empty()) {
			VIRUS cur = q.front(); q.pop();

			for (int dir = 0; dir < 4; dir++) {
				VIRUS next;
				next.y = cur.y + dy[dir];
				next.x = cur.x + dx[dir];
				next.time = cur.time + 1;

				if (next.y < 0 || next.y >= n || next.x < 0 || next.x >= n) continue;

				if ((map[next.y][next.x] == 0 || map[next.y][next.x] == 2) && visited[next.y][next.x] == -1) {
					if (map[next.y][next.x] == 0) visited[next.y][next.x] = next.time;
					else if (map[next.y][next.x] == 2) visited[next.y][next.x] = 0;
					q.push(next);
				}
			}
		}

		int candi = 0;
		bool flag = true;

		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				if (map[y][x] == 0 && visited[y][x] == -1) flag = false;

				candi = max(candi, visited[y][x]);
			}
		}

		if (flag) {
			if (res > candi) res = candi;
		}
		return;
	}

	for (int i = node; i < vec.size(); i++) {
		sel.push_back(vec[i]);
		dfs(i + 1);
		sel.pop_back();
	}
}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			scanf("%d", &map[y][x]);

			if (map[y][x] == 2) {
				vec.push_back({ y,x,0 });
			}
		}
	}

	res = 0x7fffffff;

	dfs(0);

	if (res == 0x7fffffff) res = -1;
	printf("%d\n", res);

	getchar();
	getchar();

	return 0;
}