[BOJ 17142] 연구소3 (C++)

연구소3 Gold 4

문제

전체 문제 보기

17142번: 연구소 3

접근법

이번문제는 전체 바이러스 개수(M개 이하) 중 최적의 M개의 바이러스를 선택했을 때 전파시간의 최솟값을 구하는 문제입니다. 임의의 M개를 뽑았을 때 전파시간을 계산하기 위해서는 BFS를 사용할 수 있으며, M개를 뽑기 위해서는 백트레킹을 통한 완전 탐색을 사용할 수 있습니다. 최대 바이러스 개수는 10개이므로 최악의 경우에도 \(_{10}\mathrm{C}_{5} = 252\) 가지의 경우의 수가 존재합니다. 따라서 최악의 경우에도 252번의 BFS 탐색을 진행하기 때문에 충분히 시간 내에 해결할 수 있었습니다.

구현 방법

바이러스에 대한 정의

우선 바이러스에 대해서 다음과 같이 정의하였습니다.

struct Virus {
    Virus(int _row, int _col) : row(_row), col(_col){}
    int row;
    int col;
    bool active{};
};

row, col와는 바이러스의 위치를 나타내고, active는 바이러스의 활성상태를 나타냅니다. 기본적으로 모든 바이러스는 비활성화 상태에서 시작하고, 백트레킹 과정에서 M개의 바이러스만 활성화시킵니다.

백트레킹 함수

백트래킹 함수는 다음과 같이 구현하였습니다.

int BT(Map& map, vector<Virus>& viruses, size_t idx, int dep, int M)
{
    if (dep == M)
    {
        return BFS(map, viruses);
    }
    int retval{ INF };

    for (size_t i = idx; i < viruses.size(); ++i)
    {
        viruses[i].active = true;
        retval = min(retval, BT(map, viruses, i + 1, dep + 1, M));
        viruses[i].active = false;
    }
    return retval;
}

백트레킹의 깊이는 활성화된 바이러스의 개수를 나타냅니다. 하나의 깊이에서 하나의 바이러스를 활성화하기 때문입니다. 그리고 이번에는 조합을 만들어야 하기 때문에 현재 i번째 바이러스를 활성화시켰다면 다음 깊이에서는 i+1 바이러스부터 탐색을 진행합니다. 하나의 바이러스를 활성화시킨 이후에는 재귀 호출을 통해서 다음 깊이 탐색을 이어갑니다. 그리고 활성화된 바이러스의 개수(dep)가 M이 된다면 BFS탐색을 통해서 현재 선택된 바이러스들이 연구실을 감염시키는데 필요한 시간을 계산합니다.

BFS 함수

BFS 함수는 다음과 같이 구현하였습니다.

int BFS(Map map, vector<Virus>& viruses)
{
    if (Check(map)) return 0;

    int N = map.size();
    queue<Move> q;
    for (auto& virus : viruses)
    {
        if (virus.active)
        {
            q.push(Move(virus.row, virus.col, 0));
            map[virus.row][virus.col] = -1; // 활성화 바이러스 표시
        }
    }

    int maxDep{};
    while (!q.empty())
    {
        Move cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            Move next(cur.row + dr[i], cur.col + dc[i], cur.dep + 1);
            if (next.row < 0 || next.row >= N || next.col < 0 || next.col >= N) continue; // 범위를 넘어선 경우
            if (map[next.row][next.col] == 0 || map[next.row][next.col] == -2) // 인접 노드가 빈칸이거나 비활성 바이러스인 경우
            {
                // next가 바이러스인 경우는 maxDep을 기록하지 않음.
                if (map[next.row][next.col] != -2)
                    maxDep = next.dep;

                map[next.row][next.col] = next.dep;
                q.push(next);
            } 
        }
    }
    //PrintMap(map);
    //cout << endl;
    if (Check(map))
        return maxDep;
    else 
        return INF;
}

이번 문제에서는 연구실을 감염 시키는데 소요되는 기간을 계산해야합니다. BFS의 특징상 가장 마지막에 감염시킨 깊이가 곧 우리가 구해야할 감염시키는데 필요한 기간이 됩니다. 다만, 마지막에 감염시킨 곳이 빈 공간이 아니라, 비활성화 바이러스인 경우는 제외해야 합니다. 따라서 비활성화 바이러스를 만난 경우에는 maxDep을 갱신하지 않았습니다.
그리고 BFS종료 후에 연구실이 모두 감염되었는지 확인하는 Check함수를 구현하여 감염에 성공했는지 여부를 파악하도록 하였습니다. 추가적으로 문제에서 주어진 7번 예제처럼 시작부터 모두 감염된 경우는 예외로 처리해주어야 하기 때문에 BFS시작 부분에서 Check함수를 통해서 0을 반환하도록 예외처리를 하였습니다.

전체 구현

전체 구현 코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <iomanip>
#define endl '\n'
using namespace std;
struct Virus {
    Virus(int _row, int _col) : row(_row), col(_col){}
    int row;
    int col;
    bool active{};
};
struct Move {
    Move(int _row, int _col, int _dep) : row(_row), col(_col), dep(_dep) {}
    int row;
    int col;
    int dep;
};

using Map = vector<vector<int>>;
constexpr int INF = 987'654'321;
constexpr int dr[4] = { 1,-1,0,0 };
constexpr int dc[4] = { 0,0,1,-1 };

void PrintMap(Map& map)
{
    for (auto& row : map)
    {
        for (int n : row)
        {
            if (n == INF)
                cout << setw(2)<<"*";
            else
                cout << setw(2) << n;
        }
        cout << endl;
    }
}
// 모두 감염됐는지 확인
bool Check(Map& map)
{
    for (auto& row : map)
        for (int n : row)
            if (n == 0) 
                return false;
    return true;
}
// map은 pass by value로 복사해옴
int BFS(Map map, vector<Virus>& viruses)
{
    if (Check(map)) return 0;

    int N = map.size();
    queue<Move> q;
    for (auto& virus : viruses)
    {
        if (virus.active)
        {
            q.push(Move(virus.row, virus.col, 0));
            map[virus.row][virus.col] = -1; // 활성화 바이러스 표시
        }
    }

    int maxDep{};
    while (!q.empty())
    {
        Move cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            Move next(cur.row + dr[i], cur.col + dc[i], cur.dep + 1);
            if (next.row < 0 || next.row >= N || next.col < 0 || next.col >= N) continue; // 범위를 넘어선 경우
            if (map[next.row][next.col] == 0 || map[next.row][next.col] == -2) // 인접 노드가 빈칸이거나 비활성 바이러스인 경우
            {
                // next가 바이러스인 경우는 maxDep을 기록하지 않음.
                if (map[next.row][next.col] != -2)
                    maxDep = next.dep;

                map[next.row][next.col] = next.dep;
                q.push(next);
            } 
        }
    }
    //PrintMap(map);
    //cout << endl;
    if (Check(map))
        return maxDep;
    else 
        return INF;
}

int BT(Map& map, vector<Virus>& viruses, size_t idx, int dep, int M)
{
    if (dep == M)
    {
        return BFS(map, viruses);
    }
    int retval{ INF };

    for (size_t i = idx; i < viruses.size(); ++i)
    {
        viruses[i].active = true;
        retval = min(retval, BT(map, viruses, i + 1, dep + 1, M));
        viruses[i].active = false;
    }
    return retval;
}
int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N, M; //N(4 ≤ N ≤ 50), M(1 ≤ M ≤ 10)
    cin >> N >> M;
    vector<Virus> viruses;
    Map map(N, vector<int>(N));

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            cin >> map[i][j];
            if(map[i][j] == 1)
                map[i][j] = INF;

            else if (map[i][j] == 2)
            {
                map[i][j] = -2; // 비활성 바이러스는 -2.
                viruses.emplace_back(i, j);
            }
        }

    int answer = BT(map, viruses, 0, 0, M);
    if (answer == INF) answer = -1;
    cout << answer;

    return 0;
}