백준 17142 연구소3

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

17142번: 연구소 3

 

- 브루트포스 백트래킹 + BFS 문제이다.

 

- 시간 복잡도는 BFS에 O(N^2) + 백트래킹은 10Cn의 최대값이므로, 값이 10! 이하이기에 시간초과는 나지 않는다.

 

- 먼저, map에 정보를 입력받는다. 이 때, virus의 좌표 정보는 virus 벡터에 따로 저장한다. 그 후, m개의 바이러스를 선택한다. 선택을 하는 과정은 백트래킹을 통해 진행하며, 전역변수 selected_virus에 해당 좌표를 push 해 준다. 여기서 for loop의 start 인덱스를 잘 선택 해 주어야 한다. (수의 중복 없는 경우의 수)

 

- 선택이 완료되었다면, 이제 BFS를 진행한다. 먼저 map의 정보를 temp에 복사한다. 여기서, 필자는 벽을 -2로, 비활성 바이러스를 -3으로 표시하였다. 문제에 주어진대로 *와 같은 특수문자로 표시를 하려면 char형 배열로 기록을 해야하는데, 그러면 코드가 살짝 지저분해져서이다.

 

- BFS의 시작점들을 selected_virus에서 꺼내서 queue에 넣어주고, visited를 최신화한다. 여기서 visited가 필요한 이유는 활성바이러스의 정보가 temp에 0으로 저장되어있는데, 만약 visited가 없다면 해당 좌표를 계속해서 방문할 것이기 때문에 무한루프에 빠지게 될 것이기 때문이다. 다음으로 방문여부를 체크한다. 방문을 하지 않는 조건은

 

  1. 주어진 범위를 벗어나는 경우(NxN)

  2. 벽인경우

  3. 활성 바이러스를 방문하려는 경우

  4. 현재 계산된 방문 시간이 기존에 방문했던 시간보다 더 큰 경우

 

이다.

 

- temp를 최신화하였다면, 이제 answer를 구한다. temp에서 가장 긴 시간을 정답으로 하는데, 여기서 주의해야 할 점은 해당 좌표가 비활성 바이러스의 좌표라면 continue를 해 주어야 한다는 것이다. 만약 그렇지 않으면, 가장 마지막 시간에 방문한 좌표가 비활성 바이러스인 경우에, 해당 비활성 바이러스를 방문한 시간이 answer가 될 것이다. 사실은 (그 시간-1)이 정답인데 말이다.(여기서 막혀서 결국 반례를 검색했다 ㅠㅠ) 정답을 구했다면 기존의 answer와 비교해서 최소값으로 최신화한다. 이 문제는 구현 난이도는 높지 않지만, 정답률이 확연히 낮은데 그 이유는 이러한 반례들 때문이다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, answer = -1;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
int map[50][50]; // 연구소의 정보
int temp[50][50]; // BFS 후의 연구소 정보
bool visited[50][50]; 
vector<pair<int, int>> virus;
vector<pair<int, int>> selected_virus;

bool is_active(int x, int y) { // 해당 좌표가 현재 선택된 바이러스인지를 체크
	for (int i = 0; i < selected_virus.size(); i++) {
		if (selected_virus[i].first == x && selected_virus[i].second == y) return true;
	}
	return false;
}
void update_answer() { // BFS를 마친 후, answer를 update
	int temp_answer = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 2) continue;
			temp_answer = max(temp_answer, temp[i][j]);
            // 구역의 값이 0인데, 활성 바이러스가 아니라면 바이러스가 퍼지지 않은 곳이므로 불가능한 경우의 수이다.
			if (temp[i][j] == 0 && !is_active(i, j)) return;
		}
	}
	if (answer == -1) answer = temp_answer; // 첫 가능한 경우의 수는 answer를 무조건 최신화해준다.
	answer = min(answer, temp_answer);
}

void copy() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			temp[i][j] = map[i][j];
			if (map[i][j] == 1) temp[i][j] = -2;
			if (map[i][j] == 2) temp[i][j] = -3;
		}
	}
	for (int i = 0; i < selected_virus.size(); i++) {
		temp[selected_virus[i].first][selected_virus[i].second] = 0;
	}
}

void BFS() {
	copy();
	queue<pair<int, int>> q;
	for (int i = 0; i < selected_virus.size(); i++) {
		q.push({ selected_virus[i].first, selected_virus[i].second });
		visited[selected_virus[i].first][selected_virus[i].second] = true;
	}
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 범위 밖인 경우 continue
			if (temp[nx][ny] == -2) continue; // 벽인 경우
			if (is_active(nx, ny) && visited[nx, ny]) continue; // 활성 바이러스이면서 방문 한 경우 
			if (visited[nx][ny] && temp[nx][ny] <= temp[x][y] + 1) continue; // 최소값을 가지고 있다면 continue
			temp[nx][ny] = temp[x][y] + 1;
			visited[nx][ny] = true;
			q.push({ nx,ny });
		}
	}
	memset(visited, false, sizeof(visited));
}
void DFS(int cnt, int start) {
	if (cnt == m) {
		BFS();
		update_answer();
		return;
	}
	// 백트래킹 선택
	for (int i = start; i < virus.size(); i++) {
		int virus_x = virus[i].first;
		int virus_y = virus[i].second;
		selected_virus.push_back({ virus_x, virus_y });
		DFS(cnt + 1, i + 1);
		selected_virus.pop_back();
	}
	
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) virus.push_back({ i,j });
		}
	}
	DFS(0, 0);
	cout << answer;
	return 0;
}