[골4] 14502 - 연구소

참고해서 코드 작성

#include <iostream>
#include <vector>
#include <queue>
#include <map>

#define y first
#define x second

using namespace std;
using IntPair = pair<int, int>;
using TwoDVec = vector<vector<int>>;

IntPair dir[]
{
    {  1, 0 },
    {  0, 1 },
    { -1, 0 },
    {  0, -1 }
};

TwoDVec m, vm;
vector<IntPair> vis;
int h, w, ans = 0;

// 바이러스 지도 초기화 함수
void SetMap()
{
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
            vm[i][j] = m[i][j];
    }
}

void SpreadVirus()
{
    queue<IntPair> q;

    // 위치 초기화
    for (int i = 0; i < vis.size(); i++)
        q.push(vis[i]);

    // BFS
    while (!q.empty())
    {
        auto front = q.front(); q.pop();
        int y = front.y, x = front.x;
        
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dir[i].y, nx = x + dir[i].x;

            if (ny >= h ||
                ny < 0  ||
                nx >= w ||
                nx < 0)
                continue;

            if (!vm[ny][nx])
            {
                vm[ny][nx] = 2;
                q.push({ ny,nx });
            }
        }
    }
}

// 안전 지역의 개수를 구함
int GetSafeZone()
{
    int res = 0;
    
    for (int y = 0; y < h; y++)
    {
    	for (int x = 0; x < w; x++)
    	{
            if (!vm[y][x])
                res++;
    	}
    }
    return res;
}

void DFS(int row, int cnt)
{
    if (cnt == 3)
    {
        SetMap();
        SpreadVirus();
        ans = max(ans, GetSafeZone());
        return;
    }
    // DFS
    for (int y = 0; y < h; y++)
    {
    	for (int x = 0; x < w; x++)
    	{
            // 백트래킹
            if (!m[y][x])
            {
                m[y][x] = 1;
                DFS(y, cnt + 1);
                m[y][x] = 0;
            }
    	}
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> h >> w;
    m = TwoDVec(h + 1, vector<int>(w + 1));
    vm = TwoDVec(m);

    for (int y = 0; y < h; y++)
    {
    	for (int x = 0; x < w; x++)
    	{
            cin >> m[y][x];

            if (m[y][x] == 2)
                vis.push_back({ y,x });
    	}
    }
    DFS(0, 0);
    cout << ans << endl;
    return 0;
}