백준 17142번: 연구소 3 - DFS, BFS, 백트래킹 C++코드

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

17142번: 연구소 3

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(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다.

0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다.

2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

2는 비활성화된 바이러스를 의미하고 2 중에서 m개를 선택해 바이러스를 활성화시킬 때

벽을 제외한 모든 영역이 바이러스가 되는 최소 시간을 구해야한다.

 

 

 

2.문제접근[알고리즘]

https://dingcoding.tistory.com/90

백준 14502번: 연구소 - DFS, BFS, 백트래킹 C++ 풀이

https://dingcoding.tistory.com/91

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

 

연구소 3번 문제는 연구소 1번 2번 문제와 비슷하나 가장 중요한 차이점은

초기에 모든 바이러스는 비활성화 상태라는 점이다.

문제에서 m개의 비활성화 바이러스를 선택해

벽을 제외한 모든 영역이 바이러스가 되는 최소 시간을 구해야한다.

모든 영역은 비활성화 바이러스거나 활성화 바이러스거나 상관 없이 바이러스이기만 하면 된다.

 

 

문제풀이과정

1. DFS를 통해 m개의 비활성화 바이러스를 선택해 활성화 바이러스로 만든다.

2. 선택된 활성화바이러스로 BFS를 하고, 벽을 제외한 모든영역에 바이러스를 퍼트리는 시간을 구한다.

3. DFS를 돌며 m개를 다르게 선택하며 최소 시간을 구해준다.

4. 바이러스를 어떤 방법으로도 전체 영역에 퍼트릴 수 없다면 -1, 아니면 최소시간을 출력한다.

 

 

 

3.문제풀이코드 C++

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

int n, m, arr[51][51], ans=INT_MAX, total_zero;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool ch[51][51];

bool virus_select[11];
vector<pair<int, int> > virus;
queue<pair<int,int> > Q;

void BFS() {
	int count_zero = 0;

	//활성화된 바이러스 Q에 넣어줌 
	for (int i = 0; i < virus.size(); i++) {
		if (virus_select[i] == 1) {
			Q.push({ virus[i].first, virus[i].second});
			ch[virus[i].first][virus[i].second] = 1;
		}
	}

	int time = 0;
	while (!Q.empty()) {
		int cur_size = Q.size();

		/*0인 영역에 바이러스를 다 퍼트렸는지 체크*/
		if (total_zero == count_zero) {
			ans = min(time, ans);
			while (!Q.empty()) Q.pop();
			break;
		}

		/*같은 시간에 새로 추가된 모든 바이러스를 BFS로 탐색*/
		for (int j = 0; j < cur_size; j++) {
			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] == -1) continue; //벽이면 continue
				if (ch[nx][ny] == 0) { //비활성화된 바이러스, 0인 영역 모두 방문
					ch[nx][ny] = 1;
					Q.push({ nx, ny });
					if (arr[nx][ny] == 0) count_zero++; //0인 영역을 방문한 거라면 0인 영역에 바이러스 퍼진 갯수 세줌
				}
			}
		}
		time++;
	}

	//DFS에서 또 ch를 사용하므로 BFS함수 이전 원래 상태로 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ch[i][j] = 0;
		}
	}

}

void DFS(int cur, int L) {
	if (L == m) {
		BFS();
	}
	else {
		for (int i = cur; i < virus.size(); i++) {
			virus_select[i] = 1;
			DFS(i + 1, L + 1);
			virus_select[i] = 0;
		}
	}
}

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

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

	DFS(0, 0);

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

}

백준 17142 연구소3 해결 메모리 및 시간

 

4.틀린 이유

1. 시간초과 이유 : 바이러스를 벽을 제외한 모든 영역에 퍼트렸는지 확인

/*0인 영역에 바이러스를 다 퍼트렸는지 체크*/
		if (total_zero == count_zero) {
			ans = min(time, ans);
			while (!Q.empty()) Q.pop();
			break;
		}

 

0의 개수를 세는 변수를 따로 설정해 바이러스가 된 0의 개수를 세서 비교했다.

이전에는 n*n 배열을 모두 탐색해 0이 있는지 없는지 확인해서 시간초과가 나서 틀렸다.

 

 

2. 비활성화된 바이러스도 바이러스다.

처음에 문제를 잘 이해하지 못해 모든 바이러스를 활성화 시켜야 끝나는 줄 알고 그렇게 했는데

비활성화 여부와 관계없이 모든 영역이 바이러스로 바뀌어있으면 BFS를 종료하면 된다.