[백준 17142] 연구소 3

www.acmicpc.net/problem/17142

17142번: 연구소 3

연구소 2와 비슷한 문제이다. 차이가 있다면 비활성 바이러스가 활성 바이러스를 만나면 활성바이러스가 된다는 점이다. 

비활성-> 활성바이러스가 되는 시점에선 시간+1을 해주지 않아도 된다. 활성바이러스로 부터 다시 바이러스가 퍼지기 시작하기 때문. 

 

그림으로 따지자면 다음과 같다.

위그림은 전부 빈곳 일때이다. 빈곳일때는 그냥 +1 해주면 된다. 

하지만 비활성 바이러스가 활성 바이러스가 되면 시간에 영향을 주지 않는다.

이 점만 고려하면 연구소2와 유사한 문제이다.

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

int arr[50][50];
int path[50][50];
bool visited[10];
int n, m;
int tmpResult;
int result = 3000;
struct Virus
{
  int row, col;
};

vector<Virus> vv;

bool BFS()
{
  memset(path, -1, sizeof(path));
  int dr[4] = {0, 0, -1, 1};
  int dc[4] = {1, -1, 0, 0};
  queue<Virus> q;
  for (int i = 0; i < vv.size(); i++)
  {
    if (visited[i])
    {
      q.push(vv[i]);
      path[vv[i].row][vv[i].col] = 0;
    }
  }

  while (!q.empty())
  {
    Virus cur = q.front();
    q.pop();

    for (int i = 0; i < 4; i++)
    {
      int nr = cur.row + dr[i];
      int nc = cur.col + dc[i];
      if (nr < 0 || nr > n - 1 || nc < 0 ||
          nc > n - 1 || path[nr][nc] > -1 || arr[nr][nc] == 1)
      {
        continue;
      }
      path[nr][nc] = path[cur.row][cur.col] + 1;
      q.push({nr, nc});

      if (arr[nr][nc] == 0)
      {
        tmpResult = path[nr][nc];
      }
    }
  }

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      if (arr[i][j] != 1 && path[i][j] == -1)
      {
        return false;
      }
    }
  }
  return true;
}
void DFS(int idx, int cnt)
{
  if (cnt == m)
  {
    bool flag = BFS();
    if (flag)
    {

      result = result < tmpResult ? result : tmpResult;
    };
    return;
  }

  for (int i = idx; i < vv.size(); i++)
  {
    visited[i] = true;
    DFS(i + 1, cnt + 1);
    visited[i] = false;
  }
}
int main(void)
{
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      scanf("%d", &arr[i][j]);
      if (arr[i][j] == 2)
      {
        vv.push_back({i, j});
      }
    }
  }
  DFS(0, 0);

  if (result == 3000)
  {
    printf("-1\n");
  }
  else
  {
    printf("%d\n", result);
  }
  return 0;
}