반응형
https://www.acmicpc.net/problem/17141
17141번: 연구소 2
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이
www.acmicpc.net
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 2N*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;
}
}
반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 17090번 : 미로 탈출하기 C++ 문제 풀이 (0) | 2022.02.03 |
|---|---|
| 백준 17142번: 연구소 3 - DFS, BFS, 백트래킹 C++코드 (0) | 2022.02.03 |
| 백준 14502번: 연구소 - DFS, BFS, 백트래킹 C++ 풀이 (2) | 2022.02.02 |
| 백준 15653번 : 구슬 탈출 4 , C++ 문제풀이 코드 (0) | 2022.02.02 |
| 백준 13913번: 숨바꼭질 4 - BFS, DFS 활용 (0) | 2022.02.02 |
