[백준][17142] 연구소 3

이 포스트는 백준 사이트의 연구소 3 문제 풀이입니다.

문제

해결 과정

이 문제는 조합과 탐색 을 반복적으로 수행하여 해결할 수 있습니다.

문제의 설명처럼 바이러스의 개수는 1개 이상이고 10개 이하인 개수로 지형에 존재하고
그 중 승원이가 M 개를 활성화 시켰을 때, 지형 전체에 바이러스가 전파되는 최소시간을 구하고자 합니다.

따라서 여러 바이러스 위치 중 M개를 선택하면 그에 따른 바이러스의 전파를 구현하고
전파가 지형 전체에 이뤄졌는지 확인하면서 최솟값을 구하면 됩니다.

1. 바이러스 중 M 개를 선택
2. M개의 바이러스에서 각각 전파 진행
3. 전파가 왼료된 지형에서 빈 공간임에도 감염되지 않은 곳이 있으면 1번, 없으면 4번으로
4. 전파 완료된 지형에서 가장 전파가 오래 걸린 시간 저장 및 기존 값과 비교해 최솟값 저장

위 과정을 반복적으로 수행하면 문제를 해결할 수 있습니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, M, tile_count = 0;
vector<vector<int>> board;

struct POINT {
    int row, col, dist;
};

void input(vector<POINT>& virus);
int get_shortest_diffuse_time(vector<POINT>& virus);
void diffuse_virus(vector<vector<int>>& new_board, POINT start);
int count_infect_tile(vector<vector<int>> new_board);

int main() {
    vector<POINT> virus;
    input(virus);

    cout << get_shortest_diffuse_time(virus);

    return 0;
}

void input(vector<POINT>& virus) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    board.assign(N, vector<int>(N, 0));
    for(int row = 0; row < N; ++row) {
        for(int col = 0; col < N; ++col) {
            cin >> board[row][col];
            if(2 == board[row][col]) {
                virus.push_back({row, col, 0});
                board[row][col] = -2;
            } else if(0 == board[row][col]) {
                board[row][col] = 2e9;
                tile_count += 1;
            } else if(1 == board[row][col]) {
                board[row][col] = -1;
            }
        }
    }
}

int get_shortest_diffuse_time(vector<POINT>& virus) {
    vector<bool> select(virus.size(), false);
    for(int v = 0; v < M; ++v) {
        select[v] = true;
    }

    int MIN = 2e9;
    do {
        auto new_board = board;
        vector<int> virus_nums;
        for(int i = 0; i < M; ++i) {
            if(select[i]) {
                virus_nums.push_back(i);
                diffuse_virus(new_board, virus[i]);
            }
        }

        for(int i : virus_nums) {
            new_board[virus[i].row][virus[i].col] = 0;
        }
        
        int infect_tile = count_infect_tile(new_board);
        if(infect_tile == -1) continue;
        MIN = min(MIN, infect_tile);
    } while(prev_permutation(select.begin(), select.end()));

    return (MIN == 2e9 ? -1 : MIN);
}

void diffuse_virus(vector<vector<int>>& new_board, POINT start) {
    queue<POINT> q;
    q.push(start);

    vector<vector<bool>> visited(N, vector<bool>(N, false));
    visited[start.row][start.col] = true;

    int dir_row[4]{-1, 1, 0, 0};
    int dir_col[4]{0, 0, -1, 1};

    while(false == q.empty()) {
        auto curr = q.front();
        q.pop();

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.row + dir_row[dir];
            int new_col = curr.col + dir_col[dir];

            if(new_row < 0 || new_row >= N || new_col < 0 || new_col >= N)
                continue;
            if(-1 == new_board[new_row][new_col])
                continue;
            if(visited[new_row][new_col])
                continue;
            visited[new_row][new_col] = true;

            if(-2 == new_board[new_row][new_col]) {
                q.push({new_row, new_col, curr.dist + 1});
            } else {
                new_board[new_row][new_col] = min(new_board[new_row][new_col], curr.dist + 1);
                q.push({new_row, new_col, new_board[new_row][new_col]});
            }
        }
    }
}

int count_infect_tile(vector<vector<int>> new_board) {
    int MAX = 0, infect_tile = 0;
    for(auto& row : new_board) {
        for(auto& c : row) {
            if(c == 2e9) return -1;
            else if(c == -1 || c == -2) continue;
            else MAX = max(MAX, c);
            infect_tile += 1;
        }
    }
    return (infect_tile == tile_count + M ? MAX : -1);
}

실행 결과