백준 17142 - 연구소 3(C++)

문제 링크입니다 https://www.acmicpc.net/problem/17142

17142번: 연구소 3

연구소 1과 같이 DFS를 통해서 선택, BFS를 통해서 탐색을 하는 문제였습니다.

 

문제 조건과 출력예시는 위 링크를 참고해주세요!

 

문제 접근 방법

1. 입력과 같이 바이러스의 위치와 빈칸의 갯수를 저장한다.

2. 빈 칸의 갯수가 1개 이상일 때, 바이러스를 M개 만큼 선택해준다.

3. 바이러스가 M개 선택되었다면, BFS 탐색을 통해서 바이러스를 확산시킨다.

4. 빈 칸이 없다면 T를, 빈 칸이 있다면 -1를 return 한다.

5. 최솟값을 찾아서 출력해준다. 

 

 

문제 접근 방법 - 2번 (select_virus(int start, int cnt) 함수를 참고해주세요)

DFS를 통해서 M개만큼 순서대로 선택하는 문제는 많이 나오니 기억해주세요.

(1,2,3) 이나 (3,2,1)를 선택하는 것은 문제에서 같은 방법입니다. 따라서 (1,2,3) ~ (N-2,N-1,N)번까지 순서대로 선택하면 됩니다. 

M개 만큼 선택을 했다면, 선택한 바이러스들의 좌표를 copy_map 배열에 3으로 저장합니다.

문제에서는 비활성/활성 바이러스가 나뉘어져 있음으로 3 -> 활성, 2 -> 비활성으로 저장하겠습니다.

모두 저장했다면 BFS를 통해서 탐색합니다.

 

 

문제 접근 방법 - 3번 + 4번 (bfs() 함수를 참고해주세요!)

copy_map에 활성 바이러스들의 좌표를 저장했습니다. 따라서 해당 좌표를 queue에 저장해줍니다.

4방향 탐색을 통해서 copy_map을 탐색해줍니다. 

1. 0일 경우 빈칸임으로 남은 칸의 갯수를 -1 해준 뒤, queue에 저장합니다.

2. 2일 경우 비활성 바이러스임으로 활성화 해준뒤, queue에 저장합니다.

탐색이 끝났다면, 남은 칸의 갯수를 통해서 return 해줍니다. 

 

 

문제 접근 방법 - 5번 (solve() 함수를 참고해주세요!)

mini vector에는 BFS 탐색을 하면서 걸리는 시간을 저장해줬습니다. 여기에서 최솟값을 찾은 뒤, 출력해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int map[51][51];
int copy_map[51][51]; // 2 -> 비활성 바이러스, 3 -> 활성 바이러스
int check[51][51];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int N, M;
int answer = 10000000;
int remain;
int check_virus[51][51];
vector<pair<int, int>> virus;
vector<int> Select;
vector<int> mini;
typedef struct qu {
	int x;
	int y;
	int time_;
}qu;

int bfs() {
	queue<qu> q;
	int remains = remain;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (copy_map[i][j] == 3) {
				q.push({ i,j,0 });
			}
		}
	}
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int t = q.front().time_;
		q.pop();		
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
				if (check[xx][yy] == 0 && copy_map[xx][yy] == 0) {
					check[xx][yy] = 1;
					remains--;	
					if (remains == 0) return t + 1;		
					q.push({ xx,yy,t + 1 });
				}
				if (check[xx][yy] == 0 && copy_map[xx][yy] == 2) {
					check[xx][yy] = 1;
					q.push({ xx,yy,t+1 });
				}
			}
		}
	}
    return -1;
}

void reset_map() {	
	memset(check, 0, sizeof(check));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			copy_map[i][j] = map[i][j];
		}
	}
}

void select_virus(int start, int cnt) {
	if (cnt == M) {
		for (int i = 0; i < M; i++) {
			int x = virus[Select[i]].first;
			int y = virus[Select[i]].second;
			copy_map[x][y] = 3;
		}
		mini.push_back(bfs());
		//cout << mini.back() << "\n";
		reset_map();
	}
	else{
		for (int i = start; i < virus.size(); i++) {
			if (check_virus[virus[i].first][virus[i].second] == 1) continue;
			check_virus[virus[i].first][virus[i].second] = 1;
			Select.push_back(i);
			select_virus(i, cnt + 1);
			Select.pop_back();
			check_virus[virus[i].first][virus[i].second] = 0;
		}
	}
}

void solve() {
	select_virus(0, 0);
	for (int i = 0; i < mini.size(); i++) {
		if(mini[i] >= 0) answer = min(mini[i], answer);
	}
	if (answer != 10000000) cout << answer;
	else cout << "-1";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			copy_map[i][j] = map[i][j];
			if (map[i][j] == 2) {
				virus.push_back(make_pair(i, j));
			}
			if (map[i][j] == 0) remain++;
		}
	}
	if (remain == 0) cout << "0";
	else solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!