[백준 14502] 연구소 (C#, C++) - soo:bak

문제 링크

14502번 - 연구소

설명

연구소에 바이러스가 있고, 빈 칸에 벽을 정확히 3개 세워서 바이러스 확산을 막아야 합니다. 바이러스는 상하좌우로 빈 칸에 퍼지며, 벽을 세운 후 바이러스가 퍼지지 않는 안전 영역의 최대 크기를 구하는 문제입니다.

접근법

격자 크기가 최대 8×8이고 벽은 3개만 세우므로, 모든 빈 칸 중 3개를 고르는 조합을 전부 시도해도 충분합니다.

각 조합마다 원본 맵을 복사한 뒤 선택한 세 칸에 벽을 세웁니다. 그 후 바이러스가 있는 모든 위치에서 BFS를 수행하여 바이러스를 퍼뜨립니다. 바이러스는 빈 칸으로만 이동할 수 있고 벽은 통과하지 못합니다.

BFS가 끝나면 격자에서 여전히 빈 칸으로 남아있는 칸의 개수가 안전 영역입니다. 모든 조합에 대해 이 값의 최대값을 구해 출력합니다.

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static int N, M, best = 0;
    static int[,] lab = new int[8, 8];
    static List<(int r, int c)> empties = new List<(int, int)>();
    static List<(int r, int c)> virus = new List<(int, int)>();
    static readonly int[] dr = { -1, 1, 0, 0 };
    static readonly int[] dc = { 0, 0, -1, 1 };

    static int Simulate(int w1, int w2, int w3) {
      var board = new int[8, 8];
      Array.Copy(lab, board, lab.Length);
      var walls = new[] { empties[w1], empties[w2], empties[w3] };
      foreach (var (r, c) in walls)
        board[r, c] = 1;

      var q = new Queue<(int r, int c)>();
      foreach (var v in virus)
        q.Enqueue(v);

      while (q.Count > 0) {
        var (r, c) = q.Dequeue();
        for (var d = 0; d < 4; d++) {
          var nr = r + dr[d];
          var nc = c + dc[d];
          if (nr < 0 || nr >= N || nc < 0 || nc >= M)
            continue;
          if (board[nr, nc] == 0) {
            board[nr, nc] = 2;
            q.Enqueue((nr, nc));
          }
        }
      }

      var safe = 0;
      for (var r = 0; r < N; r++) {
        for (var c = 0; c < M; c++) {
          if (board[r, c] == 0)
            safe++;
        }
      }
      return safe;
    }

    static void Main(string[] args) {
      var nm = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      N = nm[0];
      M = nm[1];
      for (var r = 0; r < N; r++) {
        var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        for (var c = 0; c < M; c++) {
          lab[r, c] = line[c];
          if (lab[r, c] == 0)
            empties.Add((r, c));
          else if (lab[r, c] == 2)
            virus.Add((r, c));
        }
      }

      var E = empties.Count;
      for (var i = 0; i < E; i++)
        for (var j = i + 1; j < E; j++)
          for (var k = j + 1; k < E; k++)
            best = Math.Max(best, Simulate(i, j, k));

      Console.WriteLine(best);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vp;

int N, M, best = 0;
int lab[8][8];
vp empties, virus;
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int simulate(int a, int b, int c) {
  int board[8][8];
  memcpy(board, lab, sizeof(lab));
  auto w1 = empties[a];
  auto w2 = empties[b];
  auto w3 = empties[c];
  board[w1.first][w1.second] = 1;
  board[w2.first][w2.second] = 1;
  board[w3.first][w3.second] = 1;

  queue<pii> q;
  for (auto v : virus)
    q.push(v);
  while (!q.empty()) {
    auto [r, c] = q.front(); q.pop();
    for (int d = 0; d < 4; d++) {
      int nr = r + dr[d];
      int nc = c + dc[d];
      if (nr < 0 || nr >= N || nc < 0 || nc >= M)
        continue;
      if (board[nr][nc] == 0) {
        board[nr][nc] = 2;
        q.push({nr, nc});
      }
    }
  }

  int safe = 0;
  for (int r = 0; r < N; r++) {
    for (int c = 0; c < M; c++) {
      if (board[r][c] == 0)
        safe++;
    }
  }
  return safe;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> N >> M;
  for (int r = 0; r < N; r++) {
    for (int c = 0; c < M; c++) {
      cin >> lab[r][c];
      if (lab[r][c] == 0)
        empties.push_back({r, c});
      else if (lab[r][c] == 2)
        virus.push_back({r, c});
    }
  }

  int E = empties.size();
  for (int i = 0; i < E; i++)
    for (int j = i + 1; j < E; j++)
      for (int k = j + 1; k < E; k++)
        best = max(best, simulate(i, j, k));

  cout << best << "\n";

  return 0;
}