[백준/C++] 17142번 연구소 3

문제

 

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

---

Algorithm

활성화 바이러스가 위치할 수 있는 지점들에 대해 완전탐색을 진행하다가,  활성화 바이러스를 m개의 지점에 위치시키면 BFS를 진행하여 바이러스가 모두 퍼지는 시간을 측정한다.

1. 재귀적 permutation() 함수를 통해, 활성화 바이러스가 초기에 위치할 m개의 지점을 정한다.
2. m개의 지점을 정했다면, BFS를 빈 공간의 갯수가 0이 될때까지 혹은 더이상 바이러스를 퍼뜨릴 수 없을 때까지 진행하여 소요 시간을 return한다.
3. 가능한 모든 지점 순열에 대해 BFS를 진행한다.
4. 모든 빈 칸에 퍼뜨릴 수 없는 경우 -1, 아니라면 BFS의 return값 중 최솟값이 최종 출력값이 된다.

 

---

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;

typedef pair<int,int> pii;

int n, m;
int cleanArea = 0;
int map[51][51];
int visitedBFS[51][51], visited[51][51];
vector<pii> virus;
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

int ans = 1e9;

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.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] == 0) cleanArea++;
        }

}

int BFS()
{
    int time = 0; //바이러스가 모두 전파되는 시간
    int ca = cleanArea; // 0이 되면 전파 완료 : return time

    queue<pii> q;
    for(int i = 0; i < virus.size(); i++)
    {
        q.push(virus[i]);
        visitedBFS[virus[i].first][virus[i].second] = 0;
    }

    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(0 <= nx && nx < n && 0 <= ny && ny < n)
            {
                if(visitedBFS[nx][ny] == -1 && map[nx][ny] != 1)
                {// 방문하지 않은 지점이면서 벽이 아니라면 바이러스 전파
                    q.push({nx,ny});
                    visitedBFS[nx][ny] = visitedBFS[x][y] + 1;
                    if(map[nx][ny] == 0) ca--;
                    time = max(time,visitedBFS[nx][ny]);
                    if(ca == 0) return time;
                }
            }
        }
    }
    return -1;
}

void permutation(int cnt, int limit, pii start)
{// 좌표 순열
    if(cnt == limit)
    {// 활성화 바이러스의 위치 순열이 정해지면 BFS 탐색 진행해 시간 측정
        memset(visitedBFS, -1, sizeof(visitedBFS));
        int bfs = BFS();
        if(bfs >= 0) ans = min(ans,bfs);
        return;
    }

    bool init = false;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            // 구성이 같은 순열 방지
            if(!init)
            {
                i = start.first;
                j = start.second;
                init = true;
            }

            if(!visited[i][j] && map[i][j] == 2)
            {
                virus.push_back({i,j});
                visited[i][j] = 1;
                permutation(cnt + 1, limit, {i,j});
                // BackTracking
                virus.pop_back();
                visited[i][j] = 0;
            }
        }
    }
}

void SOLVE()
{
    if(cleanArea == 0)
    {
        cout << 0;
        return;
    }
    permutation(0,m, {0,0});

    if(ans == 1e9) cout << -1;
    else cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}