[CodeTree] 바이러스 백신 (C++) [삼성 SW 역량테스트 기출]

https://www.codetree.ai/training-field/frequent-problems/problems/vaccine-for-virus

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, answer = 987654321;
int map[50][50];
int tmp[50][50];
int visited[50][50];

vector<pair<int, int>> hospital;
vector<pair<int, int>> picked;
bool isUsed[10];

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

void bfs(){
    int maxcount = 0;
    memset(visited, 0, sizeof(visited));

    queue<pair<int, int>> q;
    for(int i = 0; i < picked.size(); i++){
        q.push({picked[i].first, picked[i].second});
    }

    while(!q.empty()){
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if(nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny] != 1 && visited[nx][ny] == 0){
                visited[nx][ny] = visited[cx][cy] + 1;
                if(map[nx][ny] != 2) tmp[nx][ny] = 3;  // 바이러스를 제거한 자리 3으로 표시
                if(map[nx][ny] != 2 && visited[nx][ny] > maxcount) maxcount = visited[nx][ny];
                q.push({nx, ny});
            }
        }
    }

    // 남은 바이러스가 있는지 검사
    bool flag = false;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(tmp[i][j] == 0) flag = true;
        }
    }
    if(maxcount != 0 && !flag) answer = min(answer, maxcount);
}

void dfs(int depth, int start){
    if(depth == m){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                tmp[i][j] = map[i][j];
            }
        }
        bfs();
    } else{
        for(int i = start; i < hospital.size(); i++){
            if(!isUsed[i]){
                isUsed[i] = true;
                picked.push_back({hospital[i].first, hospital[i].second});
                dfs(depth + 1, start + 1);
                picked.pop_back();
                isUsed[i] = false;
            }
        }
    }
}

int main() {
    cin >> n >> m;

    int virus_cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> map[i][j];
            if(map[i][j] == 2) hospital.push_back({i, j});
            else if(map[i][j] == 0) virus_cnt++;
        }
    }
    if(virus_cnt == 0) {
        cout << 0;
        return 0;
    }

    dfs(0, 0);

    if(answer == 987654321) cout << -1;
    else cout << answer;

    return 0;
}