백준 17142번 연구소 3

🔒[문제 url]

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

🔑알고리즘

$m$개의 지점에 활성화 바이러스를 배치할 수 있는 모든 형태에 대해 BFS를 진행하여, 0인 지점이 없어질때까지 걸리는 시간 중 최솟값이 출력 답안이 된다.

1. 좌표계 순열을 설정하는 함수 permutation()을 통해 활성화 바이러스를 위치할 $m$개의 지점을 정한다.
2. BFS를 진행하여, 0인 지점이 없어지기까지 걸리는 시간time을 반환한다. 모두 없앨 수 없다면 -1을 반환한다.
3. 가능한 모든 좌표계 순열에 대해 1 2를 반복한다.
4. 반환된 $0$ 이상의 time 중 최솟값이 출력값이 된다.
$0$ 이상의 time이 반환된적이 없다면 -1을 출력한다.

🐾부분 코드

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

    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;
}

<BFS 함수>
벽이 아닌 모든 지점에 대해 바이러스를 전파한다.
0인 지점의 갯수 ca가 0이 될때까지 전파하되, 비활성 바이러스가 있는 지점2에 전파할때는 ca가 감소하지 않음에 유의한다.

void permutation(int cnt, int limit, pii start)
{
    if(cnt == limit)
    {
        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});
                virus.pop_back();
                visited[i][j] = 0;
            }
        }
    }
}

<좌표 순열 설정 함수>
활성화 바이러스를 초기에 위치시킬 $m$개의 지점을 설정한다.
$m$개가 모두 정해지면 BFS를 진행한다.

🪄전체 코드

#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;

    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)
    {
        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});
                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();
}

🥇문제 후기

전형적인 BruteForce + BackTracking 유형이었다.
이 유형은 DFS or BFS와 혼용되는 경우가 많으니 알아두자.
최근에 이 유형을 처음 접했는데, 어느덧 숙련도가 많이 올라가 만족스럽다.