Life Engineering
[BOJ 17142] 연구소 3 (C++) 본문
https://www.acmicpc.net/problem/17142
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 987654321
using namespace std;
int N, M;
int graph[51][51];
int ans = MAX;
vector<pair<int, int> > viruses;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
void bfs(vector<bool>& temp) {
int visited[51][51] = { 0, };
queue<pair<int, int> > q;
for (int i = 0; i < temp.size(); i++) {
int x = viruses[i].first;
int y = viruses[i].second;
if (temp[i]) {
visited[x][y] = 1; //활성화 바이러스
q.push({ x,y });
}
else {
visited[x][y] = -1; //비활성화 바이러스
}
}
while (!q.empty()) {
int vx = q.front().first;
int vy = q.front().second;
q.pop();
if (ans!=MAX && visited[vx][vy] - 1 > ans) //답 나온것보다 시간이 더 걸려서 퍼진 바이러스일 경우 탐색 중지
break;
for (int i = 0; i < 4; i++) {
int nx = vx + dx[i];
int ny = vy + dy[i];
if (nx<=0 || ny<=0 || nx>N || ny>N)
continue;
if (visited[nx][ny] == 0 && graph[nx][ny] == 0) {
visited[nx][ny] = visited[vx][vy] + 1; //퍼뜨림
q.push({ nx,ny });
}
if (visited[nx][ny] == -1 && graph[nx][ny] == 2) { //비활성화 바이러스 만날경우
visited[nx][ny] = visited[vx][vy] + 1;
q.push({ nx,ny });
}
}
}
bool flag = false;
int val = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (graph[i][j] == 0 && visited[i][j] == 0) {
flag = true; //virus 다 안퍼졌을때
break;
}
if (graph[i][j] == 0) {
val = max(val, visited[i][j] - 1);
}
}
}
if (!flag) {
ans = min(ans, val);
}
}
int main() {
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> graph[i][j];
if (graph[i][j]==2)
viruses.push_back({ i,j });
}
}
vector<bool> temp(viruses.size()-M, false);
temp.insert(temp.end(), M, true);
do {
bfs(temp);
} while (next_permutation(temp.begin(), temp.end()));
if (ans == MAX)
ans = -1;
cout << ans << "\n";
return 0;
}
활성화 바이러스를 놓는 모든 경우의 수를 탐색하여 최소값을 구한다.
한 case를 탐색할 때 bfs 탐색을 한다.
이 문제의 포인트는 활성화 바이러스에 인접한 비활성화 바이러스도 탐색 대상으로 큐에 넣어주는 것(비활성화 바이러스도 활성화 바이러스 만나면 활성화 되는 조건), 퍼지는 시간을 계산할 때 빈칸일때만 count 해주는 방식을 취하는 것이다.
탐색 종료 후 virus 퍼졌는지 체크하는 방식을 취해줬다.
그러나 빈칸을 탐색할 때마다 그 수를 세어줘서 그것이 빈칸의 총 갯수와 일치할 때, 바이러스가 다 퍼진 것으로 간주하면 된다.
나는 visited 배열, distance 배열을 따로 구분하지 않고 visited 배열 1개만 만들어서 했는데 이러면 코딩하기 불편하고 가독성도 떨어진다. 다른 분들의 코드(https://kimtaehyun98.tistory.com/101) 를 참조하니, visited를 아직 하지 않고 & 벽이 아닌 부분을 방문하고, 큐에 넣는다.
또한 비활성 바이러스가 아닐 경우에만(즉 빈 칸일 때만), 걸릴 수 있는 시간을 갱신해주고 빈 칸일때를 체크해서 총 빈칸의 수와 같아질 때 바이러스가 퍼졌다고 간주하며, answer 값을 갱신하는 방식이다.
또한 next_permutation으로 조합을 구하는 대신, 백트래킹을 이용해 경우의 수를 구해도 된다.
'Problem Solving' 카테고리의 다른 글
[BOJ 2589] 보물섬 (JAVA) (0) | 2022.01.04 |
---|---|
[프로그래머스] 블록 이동하기 (C++) (0) | 2021.12.16 |
[프로그래머스] 피로도 (C++) (0) | 2021.12.06 |
[프로그래머스] 방금그곡 (C++) (0) | 2021.11.28 |
[프로그래머스] 캐시 (C++) (0) | 2021.11.27 |