[백준] 14502 문제 풀이

문제

www.acmicpc.net/problem/14502

14502번: 연구소

풀이

/*
문제 풀이
1. 배열 입력
2. 원본 배열의 값이 복사된 임시 배열을 통해서 3개의 벽을 세운다.
3. 바이러스를 퍼트린다.
4. 남아있는 빈공간의 개수를 이전에 진행했던 빈 공간의 개수와 비교해서 갱신
5. 벽을 허문다.
6. 위의 2 ~ 5의 방법을 계속 반복해서 전체 경우의 수를 다 확인했다면
   계속해서 갱신된 빈 공간(0)의 개수를 출력
*/

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, result = 0;
int arr[8][8];
int tmp[8][8];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

// 2. 연구소에 바이러스를 퍼트린다. (시뮬레이션)
// bfs 기법
void bfs()
{
  int copy[8][8];
  queue<pair<int, int>> q;
  // tmp배열은 훼손되면 안되기 때문에 또 임시배열을 선언해서
  // tmp배열의 값을 임시의 임시배열에 복사한다.
  // 그리고 바이러스(2)의 위치를 기억하기 위해서 큐에 저장한다.
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      copy[i][j] = tmp[i][j];
      if (copy[i][j] == 2)
        q.push({i, j});
    }
  }
  while (!q.empty())
  {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    // 바이러스는 상하좌우로 퍼져나가기 때문에 다 비교를 해주면서
    // 만약 비교하는 공간이 빈 공간이라면 해당 위치에 바이러스(2)를 입력하고
    // 해당 위치를 큐에 넣음으로써 다음에 뿌릴 바이러스의 위치를 기억할 수 있다.
    for (int i = 0; i < 4; i++)
    {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        continue;
      if (!copy[nx][ny])
      {
        copy[nx][ny] = 2;
        q.push({nx, ny});
      }
    }
  }
  // 남아있는 빈 공간의 개수를 카운팅
  int empty = 0;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (!copy[i][j])
      {
        empty++;
      }
    }
  }
  // 이전 시뮬레이션의 빈 공간의 개수와 비교 후 갱신
  result = max(empty, result);
}

// 1. 반복문을 돌면서 연구소에 일일이 3개의 벽을 세움
// 재귀호출을 이용해서 백트래킹 기법을 구현
void build_wall(int cnt)
{
  // 밑에 있는 반복문에서 벽(1)을 3개 세웠다면 재귀호출을 빠져나간다.
  // 그리고 bfs를 호출해준다.
  if (cnt == 3)
  {
    bfs();
    return;
  }

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      // 원본 배열로부터 복사된 임시 배열에서 빈 공간(0)이 나오면 그 때부터
      // 3개의 벽을 세워준다.
      if (!tmp[i][j])
      {
        // 먼저 벽을 세운다.
        tmp[i][j] = 1;
        // 재귀 호출을 하게 되면 이전에 벽을 1개 세웠기 때문에 해당 위치를 패스하고
        // 다른 빈 공간에 벽을 세우게 될 것이다.
        build_wall(cnt + 1);
        // 이전에 build_wall함수의 재귀호출이 끝나서 3개의 벽을 세웠다면
        // 이제는 세웠던 벽을 허물어주는 작업을 진행한다.
        tmp[i][j] = 0;
      }
    }
  }
}

int main()
{
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      cin >> arr[i][j];
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      // 빈 공간(0)이 나오면 원본배열의 값들을 임시배열에 붙여넣는다.
      // 그리고 해당 위치부터 벽을 세워나가고 모든 시뮬레이션이 끝나면 벽을 해제한다.
      if (!arr[i][j])
      {
        for (int k = 0; k < n; k++)
          for (int z = 0; z < m; z++)
            tmp[k][z] = arr[k][z];
        tmp[i][j] = 1;
        build_wall(1);
        tmp[i][j] = 0;
      }
    }
  }
  // 벽 3개를 세우고 바이러스를 퍼트렸던 경우의 수 중에서 가장 많았던 빈 공간(0)의 개수를 출력
  cout << result << "\n";
  return 0;
}

여담

이 문제는 bfs, 브루트 포스 알고리즘을 사용해서 풀어야 한다. 이 연구소 문제 같은 경우에는 거의 일 수로만 따지면 4일 정도 계속 코드를 반복해서 보고, 머릿속으로 어떻게 코드의 흐름이 흘러가는지 고민했던 것 같다.