Seongkyun Han's blog
191014 백준 알고리즘 문제풀기
14 Oct 2019 | baekjoon[17142] 연구소 3
- 난이도: 상
- 문제 풀이 떠올리는데 30분, 구현까지 1시간 걸렸지만 디버깅만 주구장창 하다가 결국 틀렸다.
- 시간 초과
- 너무 조건이 많아 어렵다
- 특히, 바이러스를 퍼치는 부분이 정말 까다로웠다.
- 제일 중요한것은 문제를 정확하게 이해하고 풀기 시작하는 것 같다.
-
정확하기 이해하기 전부터 풀기 시작하다보니 결국 산으로 간다…
- 문제
- https://www.acmicpc.net/problem/17142
- NxN 크기 맵이 주어진다.
- 맵에서 바이러스들이 2, 벽이 1, 공간이 0으로 주어지며, 임의의 바이러스 M개를 골라 전체 맵에 퍼칠 경우 걸리는 최소시간을 출력.
- 맵에는 바이러스들이 활성/비활성 상태로 존재하며, M개의 바이러스만 골라 활성화 상태로 바꾼다.
- 활성화 상태가 된 바이러스는 상, 하, 좌, 우로 1초에 1칸씩 퍼져나간다.
- 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다
- 표현이 조금 애매해서 이해하는데 한참 걸렸다.
- 그러니까, 바이러스가 퍼지는 칸에는 비활성 바이러스가 있건 없건 상관이 없다.
- 모든 칸에 퍼지는 시간을 구하는것이 문제였다. 따라서 비활성 바이러스도 바이러스로 쳐야 한다.
- 문제 자체를 __모든 칸에 활성 바이러스를 퍼치는데 걸리는 시간__으로 이해해서 한참 헤멧다.
- 비활성 바이러스는 활성화 되지 않아도 바이러스다..
- 풀이
- 문제를 나누면
- 상태 맵을 입력 받는다.
- 활성화 시킬 바이러스 3개를 고르고
- BFS를 이용해 바이러스를 퍼친다.
- 다만, 1초에 1칸씩 퍼지므로 이에 유의해서 BFS를 정의해야 한다.
- 문제를 나누면
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#define MAX 2147483647
using namespace std;
int map[51][51];
int check[51][51];
int calcmap[51][51];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int answer = MAX;
int emptycnt = 0;
void init_calcmap(int N, queue<pair<int,int>> &virus)
{
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
calcmap[j][i] = check[j][i];
if (calcmap[j][i] == -2)
{//만약 바이러스 위치라면
calcmap[j][i] = 1;
virus.push(make_pair(i, j));
}
if (calcmap[j][i] != 1 && map[j][i] == 2)
{//만약 비활성화 바이러스라면 -3으로 초기화
calcmap[j][i] = -3;
}
}
}
}
void spread_virus(int N)
{
queue<pair<int, int>> virus;
init_calcmap(N, virus);
//int infect = 0;
//int time = 0;
while (!virus.empty())
{
int cx = virus.front().first;
int cy = virus.front().second;
virus.pop();
for (int i = 0; i < 4; i++)
{
int nx = cx + dx[i];
int ny = cy + dy[i];
//범위 벗어나면 끝
if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue;
if (calcmap[ny][nx] == 0)
{ // 만약 다음 위치 방문한적 없다면
//time = calcmap[ny][nx] = calcmap[cy][cx] + 1; // 방문한다.
calcmap[ny][nx] = calcmap[cy][cx] + 1; // 방문한다.
virus.push(make_pair(nx, ny));
//infect++;
}
if (calcmap[ny][nx] == -3)
{ // 만약 다음 위치가 비활성화 바이러스라면
//만약 주변에 바이러스가 꽉찻다면
int cnt = 0;
for (int k = 0; k < 4; k++)
{
int tx = nx + dx[k];
int ty = ny + dy[k];
//범위 안에서
if (tx < 0 || N <= tx || ty < 0 || N <= ty) continue;
if (calcmap[ty][tx] == 0) cnt++;
}
if (cnt == 0)
{
//time = calcmap[ny][nx] = calcmap[cy][cx];// 현재상태로 활성화
calcmap[ny][nx] = calcmap[cy][cx];// 현재상태로 활성화
virus.push(make_pair(nx, ny));
//infect++;
}
else
{
//time = calcmap[ny][nx] = calcmap[cy][cx] + 1; // 활성화
calcmap[ny][nx] = calcmap[cy][cx] + 1; // 활성화
virus.push(make_pair(nx, ny));
//infect++;
}
}
}
}
//printf("time: %d, infect: %d\n", time, infect);
int maxval = -1;
bool zero = false;
//최댓값 찾기
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
if (map[j][i] != 2 && calcmap[j][i] == 0)
{
zero = true;
//break;
return;
}
if (maxval < calcmap[j][i])
{
maxval = calcmap[j][i];
}
}
}
if (!zero && maxval < answer)
{
answer = maxval;
}
}
void virus_choose(int N, int M, int cnt)
{
if (cnt == M)
{
spread_virus(N); //바이러스 퍼치기
return;
}
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
if (check[j][i] == 0 && map[j][i] == 2)
{
check[j][i] = -2; // 바이러스 선택
virus_choose(N, M, cnt + 1);
check[j][i] = 0;
}
}
}
}
int main()
{
int N, M;
scanf("%d %d", &N, &M);
int wall = 0;
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
scanf("%d", &map[j][i]);
if (map[j][i] == 1)
{
check[j][i] = -1;
wall++;
}
}
}
//emptycnt = N * N - wall - M;
//printf("%d\n", emptycnt);
// 바이러스 고르기
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
if (check[j][i] == 0 && map[j][i] == 2)
{//바이러스 위치라면
check[j][i] = -2; // 바이러스 선택
virus_choose(N, M, 1);
check[j][i] = 0;
}
}
}
if (answer == MAX)
{
printf("-1\n");
}
else
{
printf("%d\n", answer - 1);
}
std::system("pause");
return 0;
}
- 퍼 온 간단하게 구현된 코드다…
- 출처: https://rebas.kr/846 [PROJECT REBAS]
- 복잡한 알고리즘을 간단하게 구현했다…
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
struct virus {
int x, y;
};
int a[50][50], dist[50][50];
int n, m, k, ans=1e9;
bool select[10];
vector<virus> v;
queue<virus> q;
const int dx[] = {-1, 0 , 1, 0}, dy[] = {0, 1, 0, -1};
void bfs() {
int infect=0, times=0;
while (!q.empty()) {
int x = q.front().x, y = q.front().y; q.pop();
for (int i=0; i<4; i++) {
int nx = x+dx[i], ny = y+dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (a[nx][ny] != 1 && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y]+1;
if (a[nx][ny] == 0) {
infect += 1;
times = dist[nx][ny];
}
q.push({nx, ny});
}
}
}
if (infect == k && ans > times) ans = times;
}
void solve(int idx, int cnt, int d) {
if (cnt == m) {
memset(dist, -1, sizeof(dist));
for (int i=0; i<d; i++) {
if (select[i]) {
q.push({v[i].x, v[i].y});
dist[v[i].x][v[i].y] = 0;
}
}
bfs();
return;
}
for (int i=idx; i<d; i++) {
if (!select[i]) {
select[i] = true;
solve(i+1, cnt+1, d);
select[i] = false;
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
scanf("%d", &a[i][j]);
if (a[i][j] == 2) v.push_back({i, j});
if (a[i][j] == 0) k += 1;
}
}
solve(0, 0, v.size());
printf("%d\n", ans == 1e9 ? -1 : ans);
return 0;
}