백준[baekjoon] 17142

 

www.acmicpc.net/problem/17142

17142번: 연구소 3

 

<시간복잡도 분석>

 

<문제 풀이>

문제를 해결하기 위해선 크게 2가지 함수가 필요할 것 같다.

  1. 입력에 주어진 바이러스(x) 중에서 M개의 바이러스를 선택해야 한다.  --> pick

  2. 1번에서 선택한 바이러스를 퍼트렸을 때 결과 값 반환  --> bfs

 

2번을 시도하였을 때 두 가지 결과가 발생한다.

  2-1. 모든 빈칸에 바이러스를 퍼트림

  2-2. 모든 빈칸에 바이러스를 퍼트리지 못함

 

2-2번을 판단하기 쉬운 방법은 N^2의 초기상태를 입력받을 때 빈 칸의 갯수(emptyCnt)를 미리 카운트를 한 후

2번에서 퍼트린 빈 칸의 갯수와 emptyCnt 개수의 같음 여부로 판단할 수 있다.

 

<코드>

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

const int INF = 1e9+5;
const int MAX_N = 50;
const int MAX_M = 10;

int board[MAX_N][MAX_N], dist[MAX_N][MAX_N], picked[MAX_M];
int dy[] = {-1, 1, 0, -0};
int dx[] = {0, 0, -1, 1};
int n, m, ans, vCnt, emptyCnt;
pii vPos[MAX_M];

bool OOB(int y, int x)
{
   return y < 0 || x < 0 || y >= n || x >=n;
}

int bfs()
{
   memset(dist, -1, sizeof(dist));

   queue<pii> q;
   for(int i=0; i<m; i++){
      pii p = vPos[picked[i]];
      dist[p.first][p.second] = 0;
      q.push(p);
   }

   int routeCnt = 0, infected = 0;
   while(!q.empty()){
      pii 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(OOB(ny, nx) || dist[ny][nx] != -1 || board[ny][nx] == 1) continue;

         dist[ny][nx] = dist[cur.first][cur.second] + 1;
         if(board[ny][nx] == 0){
            infected++;
            routeCnt = dist[ny][nx];
         }

         q.push({ny,nx});
      }
   }

   return infected == emptyCnt ? routeCnt : INF;
}

void pick(int idx, int prev)
{
   if(idx == m)
   {
      ans = min(ans, bfs());
      return;
   }

   for(int cur=prev+1; cur<vCnt; cur++){
      picked[idx] = cur;
      pick(idx+1, cur);
   }
}

int main()
{
   ios_base::sync_with_stdio(0), cin.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] == 0) emptyCnt++;
      if(board[i][j] == 2) vPos[vCnt++] = {i,j};
   }
   
   ans = INF;
   pick(0, -1);
   cout << (ans == INF ? -1 : ans) << '\n';
   return 0;
}