알고리즘 :: 백준 :: BFS ::14502 :: 연구소

문제

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

문제접근

푸는 방법은 다양하겠지만, 여기서는 bruteforce + BFS를 사용해서 풀었음을 밝힌다.

• 친절한 문제다. 우선, 연구소의 크기 N x M의 범위가 $1 \leq N,M\leq8$ 로 굉장히 적다.
• 최악의 경우인 8 x 8 크기의 연구소에 벽이 하나도 없고 바이러스가 2군데 있는 경우를 생각해보자. 3개의 벽을 세울 수 있는 경우는 60 x 60 x 60로 1초안에 풀 수 있음을 알 수 있다. (총 64칸, 바이러스 2칸 제외, 다른 벽 2개 제외 = 60칸)
• 벽을 놓을 수 있는 모든 경우에 대해 BFS를 수행해서 빈 공간의 개수가 가장 많은 경우를 뽑아내면 문제를 풀 수 있다.

코드

// https://www.acmicpc.net/problem/14502
#include <iostream>
#include <queue>
using namespace std;

static int N, M, lab[8][8];
static queue<pair<int, int>> virus;
static constexpr int moving[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

inline bool isSafe(int y, int x) {
    return ((0 <= y && y < N) && (0 <= x && x < M));
}

int bfs() {
    queue<pair<int, int>> q = virus;    // BFS에 사용할 임시 큐
    int tempLab[8][8];  // BFS에 사용할 임시 실험실
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < M; ++x)
            tempLab[y][x] = lab[y][x];

    while(!q.empty()) { // 바이러스 증폭 시작
        int y = q.front().first, x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int ny = y + moving[i][0], nx = x + moving[i][1];
            if (isSafe(ny, nx) && tempLab[ny][nx] == 0) {
                q.push({ny, nx});
                tempLab[ny][nx] = 2;
            }
        }
    }
    // 실험실 빈 공간 개수 카운팅 후 반환.
    int ret = 0;
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < M; ++x)
            if (tempLab[y][x] == 0) ret++;
    return ret;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> M;
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < M; ++x) {
            cin >> lab[y][x];
            if (lab[y][x] == 2) virus.push({y, x}); // 바이러스의 현재 좌표를 저장한다.
        }
    int answer = 0;
    // 벽 3개를 만들기 위해 3차 for문을 통한 bruteforce로 문제를 해결한다.
    for (int i = 0; i < M * N; ++i) {
        for (int j = i + 1; j < M * N; ++j) {
            for (int k = j + 1; k < M * N; ++k) {
                // 2차원 배열을 1차원으로 생각해야 for문 3개로 구현할 수 있다.
                int y1 = i / M, y2 = j / M, y3 = k / M;
                int x1 = i % M, x2 = j % M, x3 = k % M;
                // 세 위치 중 어느 하나라도 빈 공간이 아니라면 벽을 세울 수 없다.
                if (lab[y1][x1] != 0 || lab[y2][x2] != 0 || lab[y3][x3] != 0) continue;
                lab[y1][x1] = lab[y2][x2] = lab[y3][x3] = 1;    // 고정
                answer = max(answer, bfs());                    // 행위
                lab[y1][x1] = lab[y2][x2] = lab[y3][x3] = 0;    // 복원 (Bruteforce 3 원소)
            }
        }
    }
    cout << answer << '\n';
}

결과

• 184ms → 44ms로 단축할 수 있었던 방법
  • vector 사용을 안했다.
  • 3중 for문의 중복 인덱스 계산을 안했다.
  • 3중 for문에서 i = 0, j = 0, k = 0부터 시작하는 것이 아니라, i = 0, j = i + 1, k = j + 1로 바꿈으로써 BFS 호출 회수를 낮췄다.