연구소 3

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 1237 ~ 0109
// 10C5 = 252 * 2500 = 630,000
int N,M,ans=1e9;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int board[55][55];
int tmp[55][55];
int cost[55][55];
vector<pair<int,int>> virus;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 2)
                virus.push_back({i,j});
        }
    int ch[virus.size()];
    fill(ch, ch+virus.size(), 1);
    for(int i=0;i<M;i++) ch[i] = 0;
    do{
        queue<pair<int,int>> q;
        for(int i=0;i<N;i++)
        {
            fill(cost[i], cost[i]+N, -1);
            for(int j=0;j<N;j++)
                tmp[i][j] = board[i][j];
        }
        for(int i=0;i<virus.size();i++)
            if(ch[i] == 0)
            {
                tmp[virus[i].first][virus[i].second] = 8;
                q.push(virus[i]);
                cost[virus[i].first][virus[i].second] = 0;
            }
        int MIN = 0;            
        while(!q.empty())
        {
            auto cur = q.front(); q.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
                if(cost[ny][nx] >= 0 or tmp[ny][nx] == 1) continue;
                cost[ny][nx] = cost[cur.first][cur.second] + 1;
                q.push({ny,nx});
                if(tmp[ny][nx] != 2)
                    MIN = max(MIN, cost[ny][nx]);
                tmp[ny][nx] = 8;
            }
        }
        bool flag = true;
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
            {
                if(cost[i][j] == -1 and tmp[i][j] != 1) {
                    flag = false;
                    goto stop;
                }
            }
        stop:;
        if(flag == true) ans = min(ans, MIN);
    }while(next_permutation(ch, ch+virus.size()));
    if(ans != 1e9)
        cout << ans;
    else
        cout << -1;
    return 0;
}

• 핵심
  : next_permutation을 이용해서 전체 virus개수 중 M개를 선택하는 조합을 모두에 대해 전부 바이러스를 퍼뜨리는 경우 중 최소값을 기록

• 시간복잡도
  • 최대 10개의 바이러스 중 5개를 선택하는 수이기 때문에 252가지 경우를 가진다
  • 252가지 경우에 대해 BFS를 수행해서 총 252*(N^2) = 약 630,000번 연산 수행하니까 충분!