BOJ 14502. 연구소

BOJ 14502 연구소는 브루트포스와 BFS를 함께 쓰는 전형적인 문제다. 핵심은 벽을 세우는 모든 경우를 탐색한 뒤, 각 경우마다 바이러스 확산 결과를 시뮬레이션하는 것이다.

• 문제링크 : https://www.acmicpc.net/problem/14502

---

문제 요약

N×M 크기의 연구소 지도가 주어진다. 각 칸은 빈 칸(0), 벽(1), 바이러스(2) 중 하나다. 바이러스는 상하좌우로 인접한 빈 칸으로 계속 퍼지고, 벽은 넘지 못한다. 빈 칸 중 정확히 3곳에 새 벽을 세운 뒤 바이러스가 더 이상 퍼지지 않을 때까지 기다렸을 때, 남아 있는 빈 칸(안전 영역)의 수가 최대가 되도록 하는 것이 목표다.

입력 제한은 3 ≤ N, M ≤ 8이고, 바이러스는 2개 이상 10개 이하, 빈 칸은 3개 이상이다.

---

문제의 핵심 구조

• 빈 칸 중 3곳을 골라 벽을 세운다
• 바이러스가 상하좌우로 퍼진다
• 확산이 끝난 뒤 안전 영역의 크기를 계산한다
• 가능한 모든 벽 배치 중 최대 안전 영역을 찾는다

즉, 선택과 시뮬레이션이 결합된 문제다.

---

왜 브루트포스가 가능한가

빈 칸의 수가 아주 크지 않기 때문에, 3개의 벽을 세우는 조합을 모두 시도해도 감당 가능하다. 지도는 최대 8×8이므로 칸은 최대 64개이고, 그중 3칸을 고르는 경우의 수는 많아야 C(64, 3) = 41,664가지다. 실제로는 바이러스와 기존 벽이 있으므로 빈 칸은 이보다 적다. 경우마다 BFS 한 번이 O(NM) = 64칸 정도를 훑으므로, 네 방향 확인까지 쳐도 전체 연산은 많아야 천만 번 남짓이다. 이 문제는 최적화 트릭보다 모든 경우를 빠짐없이 생성하는 구조를 만드는 것이 우선이다.

---

바이러스 확산은 어떻게 푸는가

바이러스 위치를 시작점으로 잡고 BFS를 돌리면 된다.

• 초기 바이러스 좌표를 큐에 넣는다
• 상하좌우 빈 칸으로 퍼뜨린다
• 방문 또는 감염 처리를 한다

여기서 중요한 것은 원본 맵을 그대로 쓰지 않고, 벽 배치가 반영된 복사본에서 시뮬레이션해야 한다는 점이다.

---

구현에서 자주 틀리는 부분

원본 맵을 직접 수정하는 경우

조합을 하나 시험할 때마다 맵이 오염되면 다음 경우의 수 계산이 틀어진다. 그래서 매 시도마다 복사본을 쓰는 편이 안전하다.

벽 조합 생성과 BFS 책임을 섞는 경우

벽 조합을 만드는 로직과 바이러스 확산 로직이 섞이면 디버깅이 어려워진다. 보통은:

• 조합 생성
• 맵 복사
• BFS 확산
• 안전 영역 계산

순으로 역할을 분리하는 편이 좋다.

---

풀이 전략 요약

1. 빈 칸 좌표를 모은다
2. 3개를 고르는 조합을 만든다
3. 각 조합마다 맵을 복사하고 벽을 세운다
4. 바이러스 좌표들로 BFS를 수행한다
5. 남은 안전 영역 수를 계산한다
6. 최댓값을 갱신한다

---

참고 풀이

원래 이 글에는 코드가 없어서, 위 전략을 그대로 옮긴 참고 풀이를 C++로 덧붙인다. 같은 폴더의 다른 풀이와 같은 언어다.

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

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

int simulate() {
    int map[8][8];
    queue<pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            map[i][j] = board[i][j];          // 매 시도마다 복사본에서 시뮬레이션
            if (map[i][j] == 2) q.push({i, j}); // 모든 바이러스를 동시에 시작점으로
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (map[nx][ny] != 0) continue;   // 벽이거나 이미 감염된 칸
            map[nx][ny] = 2;
            q.push({nx, ny});
        }
    }
    int safe = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (map[i][j] == 0) ++safe;
    return safe;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    vector<pair<int, int>> empty;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> board[i][j];
            if (board[i][j] == 0) empty.push_back({i, j});
        }
    }
    int k = empty.size();
    int answer = 0;
    for (int a = 0; a < k; ++a) {
        for (int b = a + 1; b < k; ++b) {
            for (int c = b + 1; c < k; ++c) {
                board[empty[a].first][empty[a].second] = 1;
                board[empty[b].first][empty[b].second] = 1;
                board[empty[c].first][empty[c].second] = 1;
                answer = max(answer, simulate());
                board[empty[a].first][empty[a].second] = 0; // 원래대로 되돌린다
                board[empty[b].first][empty[b].second] = 0;
                board[empty[c].first][empty[c].second] = 0;
            }
        }
    }
    cout << answer << '\n';
    return 0;
}

코드 읽기

• 입력을 읽으면서 빈 칸 좌표를 empty에 모은다. 3중 반복문의 인덱스를 a < b < c로 두면 같은 세 칸을 순서만 바꿔 여러 번 시도하지 않는다.
• 세 칸에 벽을 세운 뒤 simulate()를 부르고, 끝나면 세 칸을 다시 0으로 되돌린다. 원본 board는 벽 배치를 시험하는 데만 쓰고, 바이러스 확산은 simulate() 안의 복사본 map에서 일어난다. 앞에서 말한 “원본 맵을 직접 수정하는 경우”의 함정을 이렇게 피한다.
• simulate()는 모든 바이러스 칸을 처음부터 큐에 함께 넣고 BFS를 돈다. 바이러스마다 BFS를 따로 돌릴 필요가 없다. 이 문제는 몇 초 뒤에 퍼지는지가 아니라 최종적으로 어디까지 퍼지는지만 묻기 때문에, 시작점이 여러 개여도 한 번의 탐색으로 충분하다.
• 감염된 칸을 2로 바꾸는 것이 방문 처리를 겸한다. 0인 칸만 큐에 넣으므로 같은 칸을 두 번 넣지 않는다.
• 확산이 끝난 뒤 0으로 남은 칸을 세면 그 배치의 안전 영역이다.

복잡도

빈 칸 수를 E라고 하면 시간 복잡도는 O(C(E, 3) × NM)이다. 위에서 계산했듯 제한 안에서는 충분히 빠르다. 공간은 지도 복사본과 큐에 쓰이는 O(NM)이다.

---

정리

이 문제는 “BFS 문제”이기도 하지만, 더 정확히는 조합 + 시뮬레이션 문제다. 어떤 알고리즘을 붙일지보다, 경우의 수 생성과 확산 시뮬레이션을 안정적으로 분리하는 것이 풀이의 핵심이다.