[BOJ] 17142. 연구소3

[문제]

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

[풀이]

 

17142

맞았습니다!!

2008KB

16ms

C++14 / 수정

2290

10분 전

 

1) 바이러스 후보군 (2) 는 처음에는 비활성 상태이다가 m개만큼만 활성화될 수 있다. 

 

2) 활성화된 바이러스는 상하좌우로 복제되는데 1초가 걸린다. 

 

3) 결과값 = 맵 안의 모든 칸이 바이러스가 되는 최소시간 

 

4) 맵은 빈칸(0) / 벽(1) / 바이러스 (2) 로 이루어져있다. 

 

5) 바이러스 후보군 (2) 를 모두 벡터에 넣어준다. 

dfs(활성화한 바이러스, 현재 바이러스 인덱스 ) => 바이러스 후보군 중 m개를 활성화한다. 

 

• 활성화한 바이러스 개수 == m이라면 이제 바이러스를 확산시킨다.(spreadVirus())

• 현재 바이러스 인덱스가 바이러스 후보군의 사이즈를 초과하면 함수 호출을 멈춘다. 

• 현재 활성화한 바이러스를 기준으로 추가로 m-1개를 활성화 해야 한다. (그렇기 때문에 현재 바이러스 인덱스가 필요하다.)

• 백트래킹을 사용하여 현재 인덱스의 바이러스를 활성화하고 (-1로 표시했다. ) 

  dfs(cnt+1, i+1)를 호출하여 추가로 m-1개의 바이러스를 활성화한다. 

  그리고 현재 인덱스의 바이러스를 다시 비활성화로 만들어준다. 

6) spreadVirus() => 바이러스를 확산시킨다. 확산된 칸도 -1로 만들고 큐에 넣어줌으로써 계속 확산될 수 있도록 한다. 

 

7) 전역 배열 변수인 map을 변형하지 않기 위해 복사하여 사용한다. (c_map)

---

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
int n, m, map[51][51], min_time = 987654321;
 
typedef pair<int, int> pp;
typedef pair<pp, int> ppp;
 
vector<pp> virus;
int space = 0;
 
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
 
void print()
{
    cout << '\n';
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}
void spreadVirus()
{
    queue<pp> q;
 
    bool visit[51][51];
    memset(visit, false, sizeof(visit));
 
 
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (map[i][j] == 3)
            {
                q.push(pp(i, j));
                visit[i][j] = true;
            }
            if (map[i][j] == 0) cnt++;
        }
    }
 
    int time = 0;
    while (!q.empty())
    {
        int size = q.size();
 
        if (min_time <= time)
            return;
        if (cnt == 0)
            break;
 
        while (size--)
        {
            int x = q.front().first;
            int y = q.front().second;
 
            q.pop();
 
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == 1 || visit[nx][ny])
                    continue;
 
                if (map[nx][ny] == 0)
                    cnt--;
                    
                map[nx][ny] = 3;
                visit[nx][ny] = true;
                q.push(pp(nx, ny));
            }
        }
        time++;
    }
 
    if (cnt == 0)
    {
        min_time = min(min_time, time);
    }
}
void dfs(int cnt, int cur)
{
    if (cnt == m)
    {
        //m개의 바이러스 활성화
 
        int c_map[51][51];
        memcpy(c_map, map, sizeof(map));
        spreadVirus();
        memcpy(map, c_map, sizeof(map));
 
        return;
    }
 
    if (cur >= virus.size())
        return;
 
    for (int i = cur; i < virus.size(); i++)
    {
 
        map[virus[i].first][virus[i].second] = 3;
        //활성화 바이러스는 3이라고 표시
        dfs(cnt + 1, i + 1);
        map[virus[i].first][virus[i].second] = 2;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 2)
                virus.push_back(pp(i, j));
 
            else if (map[i][j] == 0)
                space++;
        }
    }
    //input
 
    if (space == 0)
        cout << 0 << '\n';
    else
    {
        dfs(0, 0);
 
        if (min_time == 987654321)
            cout << -1 << '\n';
        else
            cout << min_time << '\n';
    }
    return 0;
}