백준 17141번 : 연구소 2 - BFS DFS 백트래킹 응용 문제

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

17141번: 연구소 2

1.문제설명

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

N*N 정사각형 배열이 주어진다. 1은 바이러스가 지나갈 수 없는 벽을 의미한다.

m은 바이러스를 놓을 수 있는 개수이고, 2는 바이러스를 놓을 수 있는 공간이다.

2가 바이러스가 놓여진 게 아니라 놓을 수 있는 공간인 점이 중요하다.

m개의 바이러스를 2가 쓰여진 공간에 두었을 때 

벽을 제외한 모든 공간에 바이러스를 퍼트린다면 

바이러스를 퍼트리는데 걸리는 최소 시간을 구해야한다.

그 최소 시간을 출력해야한다.

 

만약 바이러스 m개를 어떻게 두어도 벽을 제외한 모든 공간에 바이러스를 퍼트리지 못한다면

-1을 출력한다.

 

 

2.접근방법[알고리즘]

1. 백트래킹으로 바이러스 놓는 칸 m개 선택
2. m개를 선택했을 때 바이러스 다 퍼트릴 수 있는 지 BFS해보고 퍼트릴 수 있다면 시간을 구한다.
3. m개를 선택하는 모든 방법에 대하여 시간을 구해보고 최소 시간을 뽑는다.
4. 어떤 방법으로도 바이러스를 모든 공간에 퍼트릴 수 없다면 -1을 출력한다.

 

 

 

 

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[51][51], ans=INT_MAX;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int > > virus;
queue<pair<int, int> > Q;
//1. 바이러스 놓는 칸 m개 선택
//2. 바이러스 다 퍼트렸는지 확인
//3. 다 퍼트렸다면 최소시간 확인
//4. 다 퍼트린게 없다면 -1 출력

void print() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == -1) cout << '-' << ' ';
			else cout << arr[i][j] <<' ';
		}
		cout << '\n';
	}
	cout << "------------\n";

}

int check() {
	int minute = 0;
	//print();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == -1) continue;

			if (arr[i][j] == 0) {
				return INT_MAX;
			}
			else {
				minute = max(arr[i][j], minute);
			}
		}
	}
	return minute;
}

void BFS() {

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 1) {
				Q.push({ i,j });
			}
		}
	}

	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;
			if (arr[nx][ny] == 0) {
				arr[nx][ny] = arr[x][y] + 1;
				Q.push({ nx,ny });
			}
		}
	}
}

void initialize() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] > 1) {
				arr[i][j] = 0;
			}
		}
	}
}

void DFS(int cur, int L) {
	if (L == m) {	
		BFS();
		ans = min(ans, check());
		initialize();
	}
	else {
		for (int i = cur; i < virus.size(); i++) {
			//바이러스는 arr에서 1로 체크해준다.
			int x = virus[i].first;
			int y = virus[i].second;
			if (arr[x][y] == 0) {
				arr[x][y] = 1;
				DFS(i + 1, L + 1);
				arr[x][y] = 0;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	queue<pair<int, int > > Q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				arr[i][j] = -1;
			}
			if (arr[i][j] == 2) {
				arr[i][j] = 0;
				virus.push_back({ i,j });
			}
		}
	}


	DFS(0,0);

	if (ans == INT_MAX) {
		cout << -1;
	}
	else {
		cout << ans-1;
	}

}

백준 17141번 연구소 문제 메모리 및 시간