문제 : https://www.acmicpc.net/problem/17142
서론
DFS와 BFS를 둘 다 사용해서 구현하는데 시간이 오래걸렸음에도(약 2시간) 예상할 수 있는 반례를 예제로 주어서 비교적 쉽다는 느낌을 받았다.
아이디어
먼저 비활성 바이러스 중에 활성 바이러스 m개를 선택해서 선택된 m개를 큐에 넣고 BFS를 돌려야한다.
바이러스가 퍼지는건 시간을 체크해야하기 때문에 BFS를 사용해야한다.
문제에 나와있듯이 바이러스가 퍼질때마다(한칸씩 방문할때마다) 1초씩 증가하므로 현재 방문지 = 이전 방문지 +1 을 해주면 마지막 방문지는 최종 시간이 되므로 결과값으로 가져오면 된다.
결과값을 가져올때는 지도 전체를 방문해서 벽에 막혀 바이러스가 퍼질 수 없는 곳이 있는지 체크를 먼저 해야한다. 만약 퍼질 수 없는 곳이 있으면 시간을 결과로 가져선 안된다.
총 비활성 바이러스(지도에서 2의 개수) 중 활성 바이러스 m개를 선택하는 방법은 DFS의 완전 탐색을 이용하면 비활성 바이러스 중 활성 바이러스 m개를 선택하는 모든 경우의 수를 알 수 있는데, 이 모든 경우의 수에서 위의 BFS를 실행하면 된다. 그리고 BFS를 실행할때마다 나오는 시간중에 최솟값을 결과로 가져오면 된다. 만약 모든 BFS가 벽에 막혀 바이러스가 퍼지지 못한 곳이 있으면 -1을 출력한다.
그리고 주의해야할것이 있다.
활성 바이러스로 선택되지 못한 비활성 바이러스는 BFS 탐색 도중 활성 바이러스를 만나면 활성화된다. 그런데 어차피 활성 바이러스가 방문하면 기존에 바이러스가 있든 없든 퍼지기 때문에 무시하면 된다. 다만 비활성 바이러스가 최종 방문지면 문제가 생긴다.
문제의 세번째 테이블을 보면 7행 1열에 비활성 바이러스로 남이있는 *가 있다. 그리고 6행 1열에 7행 1열로 방문하기 직전 상태인 바이러스가 있다. 그리고 답은 6행 1열의 4초다. 즉 7행 1열을 방문하지 않고 종료한다.
이는 7행 1열까지 방문한 후 종료하도록 구현한 다음 최종 시간의 값을 가지는 방문지 모두가 비활성화 바이러스라면 결과값에서 -1을 해주면 된다. 일부가 비활성화 바이러스라면 -1을 해주면 안된다.
예제7과 같이 지도에 0이 없는 경우는 0을 출력해야한다. 지도를 입력받을 때 0의 개수를 체크해서 0이 없으면 곧바로 0을 출력하도록 한다.
구현
//c++
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
typedef struct st {
bool select;
int y;
int x;
}st;
int map[51][51];
int visit[51][51];
int n, m;
st virus[51];
int virusCnt;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
std::vector<int>result;
void bfs() {
std::queue<std::pair<int, int>>q;
memset(visit, 0, sizeof(visit));
int time = 0;
bool resultChk = true;
bool lastVisitIsVirus = true;
for (int i = 0; i < virusCnt; i++) {
if (virus[i].select == 1) {
q.push({ virus[i].y, virus[i].x });
visit[virus[i].y][virus[i].x] = 1;
}
}
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int yy = y + dy[i];
int xx = x + dx[i];
if (yy >= 0 && xx >= 0 && yy < n && xx < n && visit[yy][xx] == 0 && map[yy][xx] != 1) {
q.push({ yy,xx });
visit[yy][xx] = visit[y][x] + 1;
time = visit[yy][xx];
}
}
}
resultChk = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0 && visit[i][j] == 0) {
resultChk = false;
break;
}
else if (visit[i][j] == time && map[i][j] != 2) lastVisitIsVirus = false;
}
if (resultChk == false) break;
}
if (resultChk == true) { // 마지막 방문지가 바이러스면 시간 -1
if(lastVisitIsVirus == true) result.push_back(time - 1);
else result.push_back(time);
}
}
void dfs(int tf, int idx, int cnt) {
if (tf == 1) virus[idx].select = true;
if (cnt == m) {
bfs();
virus[idx].select = false;
return;
}
if (idx == virusCnt - 1) return;
dfs(0, idx + 1, cnt);
dfs(1, idx + 1, cnt + 1);
virus[idx].select = false;
return;
}
bool compare(int a, int b) {
if (a < b) return true;
else return false;
}
int main() {
int zeroChk = 0;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &map[i][j]);
if (map[i][j] == 2) {
virus[virusCnt].y = i;
virus[virusCnt].x = j;
virusCnt++;
}
else if (map[i][j] == 0) zeroChk++;
}
}
dfs(-1, -1, 0);
if (result.size() == 0) printf("-1");
else if (zeroChk == 0) printf("0");
else {
sort(result.begin(), result.end(), compare);
printf("%d", result[0] - 1);
}
}
최근댓글