백준 / 14502번 / 연구소 / C++

# 출처 : https://www.acmicpc.net/problem/14502

BFS를 사용하여 바이러스를 퍼뜨렸고, 재귀를 사용하여 문제에서 요구한 3개의 벽을 세웠다.

1. map에 전체 입력을 받음 (이때, 바이러스에 해당하는 2가 들어오면 바로 큐에 넣음)

2. 3개의 벽을 세우기 위해 전체를 돌며 0이 보이면 tmp에 map을 카피한 후 재귀로 3개의 벽을 세움.

즉, tmp는 최초 map의 모든 0에 벽을 세우기 위한 임시배열.

3. 벽을 다 세웠으면 BFS로 들어가서 afterWall이라는 배열에 다시 복사를 한다. 

그리고 다시 복사한 이 afterWall 배열을 가지고 바이러스를 퍼뜨린다.

4. 매 회 바이러스가 퍼진 이후 0의 개수를 세서 그 최대가 되는 때를 출력.

바이러스가 퍼진 이후 전체를 탐색하여 0의 개수를 세고싶지 않아 zeroCnt 변수를 하나 두고 이를 가지고 최대 0의 개수를 찾는데 사용하였다.

# 풀이

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#define MAX 9
 
using namespace std;
 
int R, C, zeroCnt, maxZero;
int dR[] = { 1, 0, -1, 0 };
int dC[] = { 0, 1, 0, -1 };
 
int map[MAX][MAX], tmp[MAX][MAX];
queue<pair<int, int>> baseQ;
 
bool isInRange(int row, int col)
{
    return (row >= 0 && row < R) && (col >= 0 && col < C);
}
void BFS(int& zero)
{
    int afterWall[MAX][MAX];
    memcpy(afterWall, tmp, sizeof(tmp));
    int zC = zero;
    queue<pair<int, int>> Q = baseQ;
 
    while (!Q.empty())
    {
        int cR = Q.front().first;
        int cC = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nR = cR + dR[i];
            int nC = cC + dC[i];
 
            if (isInRange(nR, nC) && afterWall[nR][nC] == 0)
            {
                afterWall[nR][nC] = 2;
                --zC;
                Q.push({ nR, nC });
            }
        }
    }
    maxZero = max(maxZero, zC);
}
 
void makeWall(int cnt, int& zero)
{
    if (cnt == 3)
    {
        BFS(zero);
        return;
    }
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            if (tmp[i][j] == 0)
            {
                tmp[i][j] = 1;
                --zero;
                makeWall(cnt + 1, zero);
                tmp[i][j] = 0;
                ++zero;
            }
        }
    }
}
int main()
{
    cin >> R >> C;
    zeroCnt = R * C;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
        {
            cin >> map[i][j];
            if (map[i][j] != 0)
            {
                --zeroCnt;
                // 바이러스의 위치는 한 번 입력이 들어오면
                // 변하지 않으므로 baseQ에 담아두고 
                // BFS에선 Q에 복사하여 사용
                if (map[i][j] == 2)
                    baseQ.push({ i, j });
            }
        }
 
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            // 0 발견시 연구실 상태를 복사한다.
            if (map[i][j] == 0)
            {
                memcpy(tmp, map, sizeof(map));
                tmp[i][j] = 1;
                --zeroCnt;
                makeWall(1, zeroCnt);
                tmp[i][j] = 0;
                ++zeroCnt;
            }
        }
    }
 
    cout << maxZero << endl;
    return 0;
}