본문 바로가기
알고리즘 문제풀이/백준

[백준 17141] 연구소 2

by m2162003 2020. 12. 19.

www.acmicpc.net/problem/17141

 

17141번: 연구소 2

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이

www.acmicpc.net

dfs + bfs 문제이다.

대부분의 구현 문제와 유사하게 backtracking을 사용하여 연구소를 선택하고 m = cnt라면 bfs를 진행하는 구조이다. 

문제 특성상 이차원배열 2개를 사용하는 것이 좋다. 

하나는 벽과 빈곳, 연구소를 표현하기 위한 오리지널 배열과 바이러스가 퍼지는 경로를 나타내는 배열 2가지가 필요하다.

 

경로 배열은 bfs시작시마다 매번 초기화해줘야 한다. 아니면 이전 경로가 저장되어 값이 잘못나온다.

 

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

struct V
{
  int row, col;
};

using namespace std;

int arr[50][50];
int path[50][50];
V arrv[10];
bool visited[10];
int n, m;
int sze;
int ans = 300;
queue<V> q;

int BFS()
{
  memset(path, 0, sizeof(path));
  for (int i = 0; i < sze; i++)
  {
    if (visited[i])
      q.push(arrv[i]);
  }

  int dr[4] = {0, 0, -1, 1};
  int dc[4] = {1, -1, 0, 0};

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

    for (int i = 0; i < 4; i++)
    {
      int nextR = cur.row + dr[i];
      int nextC = cur.col + dc[i];

      if (nextR < 0 || nextC < 0 || nextR > n - 1 || nextC > n - 1)
        continue;

      if (arr[nextR][nextC] == 0 && path[nextR][nextC] == 0)
      {
        path[nextR][nextC] = path[cur.row][cur.col] + 1;
        q.push({nextR, nextC});
      }
    }
  }

  int result = 0;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      if (arr[i][j] == 0 && path[i][j] == 0)
      {
        return 300;
      }
      result = result < path[i][j] ? path[i][j] : result;
    }
  }
  return result;
}

void BackTracking(int idx, int cnt)
{
  if (cnt == m)
  {
    int tmp = BFS();
    ans = ans > tmp ? tmp : ans;
    return;
  }

  for (int i = idx; i < sze; i++)
  {
    visited[i] = true;
    arr[arrv[i].row][arrv[i].col] = 1;
    BackTracking(i + 1, cnt + 1);
    arr[arrv[i].row][arrv[i].col] = 0;
    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)
      {
        arrv[sze++] = {i, j};
        arr[i][j] = 0;
      }
    }
  }

  BackTracking(0, 0);

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

 

댓글