문제
https://www.acmicpc.net/problem/17142
풀이
바로 전에 풀었던 문제와 마찬가지로 완전탐색으로 풀면 되는 문제이다. 거기에다가 bfs 끼얹기 정도? 이번에는 조합에 대한 시간이 10 이하기 때문에 거의 상수로 생각해줘도 되서 연구소 보다 시간이 많이 줄어들었다.
다만 이 문제는 시간 마다 증식되는 칸을 알아야해서 bfs로 문제를 풀어야 하고 무엇보다도 활성 바이러스, 비활성 바이러스에 대한 처리를 해주는게 관건이다. 처음에는 비활성 바이러스는 큐에 넣지 않고 그냥 활성 바이러스와 같은데 큐에 넣지만 않고 처리했는데 이렇게 하니까 비활성 바이러스를 만났을때 큐에 넣어야 하는데 넣지 않고 진행하게 되었다. 또 그렇다고 빈칸도 동일하게 취급하면 안되는게 문제 결과는 그냥 모든 빈칸에 바이러스를 채워햐 하기 때문에 이를 고려해야 한다. 따라서 시간 갱신 없이 바이러스 개수 추가 없이 큐에 넣어줘서 해결해주면 된다.
마지막 처리를 안해줘서 5분은 더 시간 투자를 한 것 같다.
실수
- 코드 작성 속도 느림
- 비활성 바이러스 처리에 대해 생각을 안함.
- stl 사용 미숙
코드
#define _CRT_SECURE_NO_WARNINGS
#define BLANK 0
#define WALL 1
#define VIRUS 2
#define NON_ACTIVATION_VIRUS 3
#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
using namespace std;
int n, m;
int wall_num; // 사실상 필요없음, 전문제랑 헷갈림
int virus_num; // 바이러스 개수(증식 포함)
int result = 2500; // 가능한 최소 시간은 2500
int temp_result;
vector<vector<int>> matrix(51, vector<int>(51, 0));
vector<pair<int, int>> wall_location;
vector<pair<int, int>> virus_location;
vector<pair<int, int>> dir;
vector<int> combination; // 순열용
queue<pair<pair<int,int>, int>> que;
void bfs() {
for (int i = 0; i < combination.size(); i++) {
if (combination[i] == 1) {
que.push(make_pair(virus_location[i], 0));
}
else { // 비활성화 바이러스도 큐에 넣어줘야 함
matrix[virus_location[i].first][virus_location[i].second] = NON_ACTIVATION_VIRUS;
}
}
while (!que.empty()) {
pair<int, int> location = que.front().first;
int t = que.front().second;
que.pop();
for (int i = 0; i < 4; i++) {
int x = location.first + dir[i].first;
int y = location.second + dir[i].second;
if (1 <= x && x <= n) {
if (1 <= y && y <= n) {
if (matrix[x][y] == BLANK) {
que.push(make_pair(make_pair(x, y), t + 1));
matrix[x][y] = VIRUS;
virus_num++;
temp_result = t + 1;
}
if (matrix[x][y] == NON_ACTIVATION_VIRUS) { // 이것도 큐에 넣어줘야함. 근데 이걸로 인해서 시간 갱신 하면 안됨
que.push(make_pair(make_pair(x, y), t + 1));
matrix[x][y] = VIRUS;
}
}
}
}
}
}
int main() {
dir.push_back(make_pair(1, 0));
dir.push_back(make_pair(0, 1));
dir.push_back(make_pair(-1, 0));
dir.push_back(make_pair(0, -1));
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf(" %d", &matrix[i][j]);
if (matrix[i][j] == WALL)
wall_location.push_back(make_pair(i, j));
if (matrix[i][j] == VIRUS)
virus_location.push_back(make_pair(i, j));
}
}
for (int i = 0; i < virus_location.size() - m; i++) {
combination.push_back(0);
}
for (int i = 0; i < m; i++) {
combination.push_back(1);
}
do {
//초기화
wall_num = wall_location.size();
virus_num = virus_location.size();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
matrix[i][j] = BLANK;
}
}
for (int i = 0; i < wall_location.size(); i++) {
matrix[wall_location[i].first][wall_location[i].second] = WALL;
}
for (int i = 0; i < virus_location.size(); i++) {
matrix[virus_location[i].first][virus_location[i].second] = VIRUS;
}
for (; !que.empty();)
que.pop();
//bfs
bfs();
// 빈칸 모두 채우고 최소면 저장
if (virus_num == (n * n - wall_num) && temp_result < result)
result = temp_result;
} while (next_permutation(combination.begin(), combination.end()));
if (result == 2500) // 안바뀌었으면 경우의수가 없는 것
printf("-1");
else
printf("%d", result);
return 0;
}
기록용 블로그