[BOJ/C++] 백준 14502번: 연구소

Introduction

---

14502번: 연구소

 

이번 포스트에서는 백준 14502번, 연구소 문제를 풀어보겠습니다. 최대 $8{\times}8$ 크기의 이차원 배열을 이용한 Simulation 문제입니다.

 

입력	→ 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. → $3 \leq N, M \leq 8$ → 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. → 0은 빈 칸($\geq 3$), 1은 벽, 2는 바이러스 위치이다. → $2 \leq$ 바이러스 개수 $\leq 10$
조건	→ 연구소의 크기는 $N \times M$이다. → 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나간다. → 새로 세울 수 있는 벽의 개수는 3개이다. → 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라 한다. → 안전 영역 크기의 최댓값을 구해라.
출력	→ 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

 

Planning

---

이번 문제는 잘 보면 크게 두 파트로 나눌 수 있습니다. 아래의 두 기능을 얼마나 효율적으로 구성하는지가 문제 통과 여부를 결정하죠.

 

1. 3개의 벽을 세우는 파트
2. 바이러스가 퍼져나가는 파트

 

우선 3개의 벽을 세우는 부분은 가능한 모든 조합을 찾는 문제와 같습니다. 어디서 많이 본 표현이지 않나요? 네, 바로 DFS 문제를 적용할 때 필요한 구절입니다. 하나 주의할 점은 벽을 세우는 순서는 전혀 상관없다는 점입니다. 따라서 순서는 크게 중요하지 않죠. 즉, 중복을 허용하지 않는 DFS 문제입니다. 이 점을 유의해 문제를 풀 수 있도록 합시다.

두 번째는 바이러스가 퍼져나가는 부분입니다. 바이러스가 상하좌우로 퍼져나가며, 더 이상 전파시킬 수 없어야 종료됩니다. 이 부분은 DFS/BFS 모두 가능하지만, 상하좌우로 퍼져나가는 모습을 잘 나타낼 수 있는 BFS로 풀어봅시다. 어차피 연산량에서는 큰 차이가 없을 겁니다. 갈 수 있는 모든 곳을 구해야 하는 것은 같기 때문이죠.

자, 이제 3개의 벽을 세우는 파트는 DFS, 바이러스가 퍼져나가는 부분은 BFS로 결정했습니다. 사실 이 문제를 풀면서 스스로 질문을 많이 던졌는데요. 아래는 그 중 일부를 발췌했습니다.

 

	Question	Answer
1	BFS가 맞을까? (Depth가 얕다고 적게 전파하지 않는다.)	벽이 3개밖에 되지 않아 depth가 더 중요해 보임 → BFS
2	벽을 어떻게 골라야 할까?	$_{3}^{n_0}\textrm{C}$
3	전파를 어떻게 표현할지?	Flag, or Queue
4	DFS를 써도 괜찮을까? (조금의 규칙을 추가하면 연산량을 크게 줄일 수 있다)	예상치 못한 버그가 생길 수 있고, 연산량이 감당 가능할 정도로 보임 → DFS

 

사실 이 중 DFS에 대한 의문이 가장 컸었습니다. 그래서 연산량을 고려해보니 충분히 메모리, 시간제한 안쪽으로 들어올 것으로 예상되더군요. DFS가 탐색해야 할 연산량은 아래와 같습니다.

$$2^6 \times (2^6-1) \times (2^6-2) \times t_{node} \approx 2^{18} \times t_{node}$$

여기서 $t_{node}$는 DFS node 1개의 연산 처리시간입니다. 이 정도면 제한 시간인 2초를 충분히 견딜 수 있어 보입니다. 그렇기에 망설임 없이 DFS를 쓰기로 결정하고 작성한 Pseudo code는 아래와 같습니다.

 

void deepCopy();     // to avoid shallow copy
void generateWall(); // generate 3 wall
void spreadVirus();  // spread virus after generateWall()

int main() {
  // get input N, M
  // get original map with marking initial position of virus
  // generate wall via DFS
  // if count == 3, copy map1 into map2
  // spread virus
  // queue empty → count safe area
  // print answer
}

 

Source Code

---

/**
 * @file q14502.cpp
 * @author YoungJ-Baek (qordudwls1@gmail.com)
 * @brief solution for BOJ #14502, https://www.acmicpc.net/problem/14502
 * @version 0.1
 * @date 2023-03-19
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <iostream>
#include <queue>
#include <vector>
#define MAX 8

using namespace std;

int N, M, answer;
int map1[MAX][MAX],
    map2[MAX][MAX];  // map1 for original map, map2 for virus spreading
vector<pair<int, int>> virus_initial;              // initial location of virus
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};  // virus movement -> use pair

void deepCopy(int src[MAX][MAX], int dst[MAX][MAX]);  // to avoid shallow copy
void generateWall(int count, int start);              // generate 3 wall
void spreadVirus();  // spread virus after generateWall()

int main() {
  // get input
  cin >> N >> M;
  for (int row = 0; row < N; row++)
    for (int col = 0; col < M; col++) {
      cin >> map1[row][col];
      if (map1[row][col] == 2)
        virus_initial.push_back(
            make_pair(row, col));  // mark initial position of virus
    }
  generateWall(0, 0);
  cout << answer;
  return 0;
}

/**
 * @brief Copy 2d array from src to dst, avoiding shallow copy
 *
 * @param src source 2d array
 * @param dst destination 2d array
 */
void deepCopy(int src[MAX][MAX], int dst[MAX][MAX]) {
  for (int row = 0; row < N; row++)
    for (int col = 0; col < M; col++) dst[row][col] = src[row][col];
}

/**
 * @brief Generate 3 wall with DFS, then toss map to spreadVirus()
 *
 * @param count depth of wall
 * @param start start index to reduce repetitive operation
 */
void generateWall(int count, int start) {
  if (count == 3) {
    deepCopy(map1, map2);
    spreadVirus();
  } else {
    for (int row = start; row < N; row++)
      for (int col = 0; col < M; col++)
        if (map1[row][col] == 0) {
          map1[row][col] = 1;
          generateWall(count + 1, row);
          map1[row][col] = 0;
        }
  }
}

/**
 * @brief Spread virus via BFS, and compare safe area with answer
 *
 */
void spreadVirus() {
  queue<pair<int, int>> virus_queue;
  for (int index = 0; index < virus_initial.size(); index++)
    virus_queue.push(virus_initial[index]);

  while (!virus_queue.empty()) {
    int y = virus_queue.front().first;
    int x = virus_queue.front().second;
    virus_queue.pop();

    for (int index = 0; index < 4; index++) {
      int ny = y + dy[index];
      int nx = x + dx[index];

      if (ny >= 0 && ny < N && nx >= 0 && nx < M && map2[ny][nx] == 0) {
        map2[ny][nx] = 2;
        virus_queue.push(make_pair(ny, nx));
      }
    }
  }
  int safe_area = 0;
  for (int row = 0; row < N; row++)
    for (int col = 0; col < M; col++)
      if (map2[row][col] == 0) safe_area += 1;
  answer = safe_area > answer ? safe_area : answer;
}

 

Note

---

 

ChatGPT

---

이 문제는 ChatGPT가 계속 뻗어버려 완전한 코드를 얻지는 못했습니다. 문제를 좀 더 부분적으로 쪼개서 답을 얻어보도록 할 예정이니 추후 업데이트 된 내용을 확인해 주세요. 아래는 만들다 만 코드이며, 의도가 무엇인지는 알겠으나 좀 더 분석이 필요해 보이네요.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 8;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int N, M;
int map[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

int dfs(int x, int y) {
    visited[x][y] = true;
    int cnt = 1;
    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 (visited[nx][ny] || map[nx][ny] == 1) continue;
        cnt += dfs(nx, ny);
    }
    return cnt;
}

int getSafeArea() {
    int safeArea = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visited[i][j] = false;
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 2 && !visited[i][j]) {
                safeArea += dfs(i, j);
            }
        }
    }
    return safeArea;
}

int main() {
    cin >> N >> M;
    vector<pair<int, int>> emptyPos;
    vector<int> wallPos(3, 0);
    int emptyCnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 0) {
                emptyPos.push_back({i, j});
                emptyCnt++;
            }
        }
    }
    int ans = 0;
    do {
        for (int i = 0; i < 3; i++) {
            map[emptyPos[wallPos[i]].first][emptyPos[wallPos[i]].second] = 1;
        }
        ans = max(ans, emptyCnt - getSafeArea() - 3);
        for (int i = 0; i < 3; i++) {
            map[emptyPos[wallPos[i]].first][

 

Reference

---

GitHub - YoungJ-Baek/algorithm-study