[Baekjoon][17142] 연구소 3

출처 - 백준사이트

17142번: 연구소 3

나의 풀이

BFS와 DFS를 조합하는 문제로, 구현은 어렵지 않으나 바이러스를 퍼트리는 과정에서 '비활성화 바이러스'의 처리가 중요한 문제.
비활성화 바이러스를 처리하는 과정에서 고려해야 할것.

1. 비활성화 바이라스가 있는 자리도 바이러스가 퍼진 자리로 생각.
   4 2
   1 1 1 1
   1 2 2 1
   1 2 2 1
   1 1 1 1 Answer : 0
2. 1의 연장선인데 바이러스가 반칸에 모두 퍼진시간 < 비활성화바이라스가 활성화 된 후 퍼진 시간일 경우는 바이러스가 빈칸에 모두 퍼진 시간으로 끝나야 함
   5 1
   0 2 2 2 2
   0 1 2 2 2
   0 1 2 2 2
   0 1 2 2 2
   0 1 2 2 1 Answer : 5

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

#define MAX_SIZE    50

using namespace std;

const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};

int N, M;
int map[MAX_SIZE][MAX_SIZE];
int tempmap[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
int result = 0x7fffffff;
int remain_zero = 0, temp_remain_zero = 0;
vector<pair<int,int>> virus;
vector<pair<int,int>> picked_virus;
queue<pair<int,int>> spread_virus;

void spreadVirus(int y, int x) {
    for (int i = 0 ; i < 4 ; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (0 <= ny && ny < N && 0 <= nx && nx < N) {
            if ((!visit[ny][nx] && tempmap[ny][nx] == 0) || (!visit[ny][nx] && tempmap[ny][nx] == 2)) {
                if (tempmap[ny][nx] == 0)
                    temp_remain_zero--;

                spread_virus.push({ny, nx});
                tempmap[ny][nx] = 3;
                visit[ny][nx] = true;
            }
        }
    }
}

void pickVirus(int num) {
    if (picked_virus.size() == M) {
        int time = 0;
        temp_remain_zero = remain_zero;
        memcpy(tempmap, map, sizeof(tempmap));
        memset(visit, false, sizeof(visit));

        for (int idx = 0 ; idx < picked_virus.size() ; idx++) {
            spread_virus.push({picked_virus[idx].first, picked_virus[idx].second});
            tempmap[picked_virus[idx].first][picked_virus[idx].second] = 3;
            visit[picked_virus[idx].first][picked_virus[idx].second] = true;
        }

        while (!spread_virus.empty()) {
            int cnt = spread_virus.size();

            if (temp_remain_zero == 0)
                break;

            while (cnt > 0) {
                spreadVirus(spread_virus.front().first, spread_virus.front().second);
                spread_virus.pop();
                cnt--;
            }

            time++;
        }

        while (!spread_virus.empty())
            spread_virus.pop();

        if ((temp_remain_zero == 0) && (result > time))
            result = time;

        return ;
    }

    for (int idx = num ; idx < virus.size() ; idx++) {
        picked_virus.push_back(virus[idx]);
        pickVirus(idx+1);
        picked_virus.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(), cin.tie(0), cout.tie(0);

  cin >> N >> M;

    for (int y = 0 ; y < N ; y++) {
        for (int x = 0; x < N ; x++) {
            cin >> map[y][x];

            if (map[y][x] == 2)
                virus.push_back({y,x});
            else if (map[y][x] == 0)
                remain_zero++;
        }
    }

    pickVirus(0);

    if (result != 0x7fffffff)
        cout << result << endl;
    else
        cout << -1 << endl;;

    return 0;
}