백준 17141 - 연구소 2
Updated:
C++
17141번 - 연구소 2
문제
연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자. 문제 출처
접근 방법
DFS와 BFS 둘 다 사용하여 해결한다. 해결하는 과정은 다음과 같다.
- 모든 바이러스의 좌표를 저장 한다.
- DFS를 이용하여 m개의 바이러스의 좌표를 뽑는다.
- 뽑은 바이러스의 좌표를 시작으로, BFS를 통해 연구소에 퍼트린다.
- 이 그래프에서 바이러스가 퍼진 시간의 최댓값을 계산하고, 이 최대값이 이전에 DFS로 뽑은 바이러스가 퍼뜨린 최대 시간보다 작으면 갱신한다.
- 2번으로 돌아와 바이러스를 뽑는 모든 경우의 수를 반복한다.
구현
Main()
연구소의 정보를 입력받으며, 바이러스를 뜻하는 2가 발견되면 virusPossi 벡터에 입력한다.
또한 벽을 인식하면(1) visited와 saved 배열의 그 위치에 1을 저장해준다.
saved를 또한 추가로 저장해주는 이유는, DFS를 통해 여러번 그래프를 탐색 할 때 초기화 시켜주어야 하기 때문이다.
DFS()
바이러스가 들어 갈 수 있는 자리 중, m개의 바이러스를 뽑도록 해주는 함수이다.
sel배열에 저장하며 뽑는데, 이 배열의 인덱스는 lv이며 이는 총 뽑은 바이러스의 개수라고 생각하면 된다.
탈출 조건으로 lv이 m과 같으면 통과하고, 조건문을 통과하면 BFS()함수를 호출하고, getResult를 통해 최대 걸린 시간을 계산한다.
이후 init으로 초기 상태로 초기화 한다.
BFS()
뽑은 m개의 바이러스 좌표를 시작 기점으로 연구소 모든 곳에 퍼트리는 함수이다.
m개의 시작 바이러스의 좌표에 visited 인자를 1로 해주어, 여기는 이미 바이러스가 존재하고 있다고 인식시켜준다.
이후 두 개의 while문을 사용하는데, 바깥쪽의 while은 한 시점을 뜻한다. 즉, 여러 바이러스가 동시에 퍼뜨리는데, 이때의 시간을 의미한다. 이는 t를 통해 구현하였다.
따라서 k개의 바이러스가 동시에 퍼뜨리는 것을 구현하기 위해, vc를 통해 현재 시점의 바이러스 개수를 세고, vc만큼 내부 while문을 반복하여 바이러스를 퍼뜨린다.
바이러스를 퍼뜨릴 때, 현재 바이러스의 위치에서 상 하 좌 우 만큼 이동한다.
만약 visited가 0이며 방문하지 않았다고 표시 되면, 그 좌표를 1로 설정하여 방문하였다고 표기하고 새로운 바이러스 좌표로 등록한다.
또한 그 위치에 시점을 나타내는 time배열을 통해, 이 위치에 바이러스가 몇 시간만에 퍼뜨렸는지를 저장한다.
코드 - Back Tracking
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 999999999;
int n, m, v, result = MAX;
int graph[50][50], sel[10], time[50][50];
int visited[50][50], saved[50][50];
bool success = false;
vector<pair<int, int>> virusPossi;
void DFS(int lv, int idx);
void BFS();
void print();
void getResult();
void init();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
if(graph[i][j] == 2)
virusPossi.push_back(make_pair(i, j));
else if (graph[i][j] == 1) {
visited[i][j] = true;
saved[i][j] = true;
}
}
}
v = virusPossi.size();
DFS(0, 0);
if (success)
cout << result;
else
cout << -1;
}
void DFS(int lv, int idx) {
if (lv == m) {
BFS();
getResult();
init();
return;
}
for (int i = idx; i < v; i++) {
sel[lv] = i;
DFS(lv + 1, i + 1);
}
}
void print() { //m개의 바이러스를 제대로 뽑았는지 확인하기 위한 함수. 결과에는 영향이 없다.
for (int i = 0; i < m; i++) {
cout << sel[i] << " ";
}
cout << "\n";
}
int goy[4] = { -1, 1, 0 ,0 };
int gox[4] = { 0, 0, -1, 1 };
void BFS() {
queue<pair<int, int>> virus;
int y, x, cury, curx;
for (int i = 0; i < m; i++) {
virus.push(virusPossi.at(sel[i]));
y = virusPossi.at(sel[i]).first;
x = virusPossi.at(sel[i]).second;
visited[y][x] = true;
}
int t = 1, vc;
while (!virus.empty()) {
vc = virus.size();
while (vc--) {
y = virus.front().first;
x = virus.front().second;
virus.pop();
for (int i = 0; i < 4; i++) {
cury = y + goy[i];
curx = x + gox[i];
if (-1 < cury && cury < n && -1 < curx && curx < n && !visited[cury][curx]) {
virus.push(make_pair(cury, curx));
visited[cury][curx] = true;
time[cury][curx] = t;
}
}
}
t++;
}
}
void getResult() {
int maxNum = 0;
bool failed = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (time[i][j] > 0) {
maxNum = max(maxNum, time[i][j]);
}
else if (visited[i][j] == 0)
failed = true;
}
}
if (!failed) { //모든 빈 칸에 바이러스를 퍼뜨렸다.
result = min(maxNum, result);
success = true;
}
}
void init() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = saved[i][j];
time[i][j] = 0;
}
}
}
후기 및 개선할 점
시간이 조금 걸렸지만, 이전에 풀었던 방식을 합하기만 하면 어렵지 않은 문제였다.
