[Baekjoon] 14502. 연구소

문제 링크

2차원 좌표에서 바이러스와 벽, 그리고 빈공간이 있을 때, 빈 공간에 3개의 벽을 세워 안전 지역(바이러스가 닿을 수 없는 공간)의 최대값을 구하는 문제이다.

구현해야 할 코드를 나누어 보면 총 3가지이다.

1. 빈 공간들 중에서 벽을 세울 3칸 선택하기
2. 벽을 세운 상태에서 바이러스를 퍼뜨려 안전지역의 크기 구하기
3. 다시 1번으로 돌아가서 다른 조합의 벽을 선택하기

처음에는 벽을 놓는 부분에 대해 복잡하게 생각했는데, 전체 좌표의 크기가 최대 8x8이라 최악의 경우가 64x64x64x(BFS)인데 이정도면 시간초과가 발생할 정도는 아닌 것 같아 전체 빈 공간들 중 3개를 선택하는 모든 경우의 수에 대해 BFS를 실행하는 방법으로 구현하였다.

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct p
{
    int x;
    int y;
};

p make_p(int x, int y)
{
    p temp;
    temp.x = x;
    temp.y = y;
    return temp;
}

int N, M;
int myMap[9][9];
bool visited[9][9];

int answer;

vector<p> space;
vector<p> virus;
queue<p> q;
int path[64 * 64 * 64];

void bfs()
{
    for (int i = 0; i < virus.size(); i++)
    {
        q.push(virus[i]);
        myMap[virus[i].x][virus[i].y] = true;
        visited[virus[i].x][virus[i].y] = true;
    }

    while (!q.empty())
    {
        p cur = q.front();
        q.pop();

        for (int k = 0; k < 4; k++)
        {
            int next_x = cur.x + dx[k];
            int next_y = cur.y + dy[k];

            if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && !visited[next_x][next_y] && myMap[next_x][next_y] == 0)
            {
                q.push(make_p(next_x, next_y));
                visited[next_x][next_y] = true;
            }
        }
    }
}

void build_wall(int idx)
{
    if (idx == 3)
    {
        for (int i = 0; i < 3; i++)
        {
            myMap[space[path[i]].x][space[path[i]].y] = 1;
        }
        
        memset(visited, 0, sizeof(visited));

        bfs();

        int safe_zone = 0;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (!visited[i][j] && myMap[i][j] == 0)
                    safe_zone += 1;
            }
        }

        if (safe_zone > answer)
            answer = safe_zone;

        for (int i = 0; i < 3; i++)
        {
            myMap[space[path[i]].x][space[path[i]].y] = 0;
        }
    }
    else
    {
        for (int i = 0; i < space.size(); i++)
        {
            if (idx == 0 || path[idx - 1] < i)
            {
                path[idx] = i;
                build_wall(idx + 1);
            }
        }
    }
}

int main()
{
    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            int x;
            cin >> x;

            myMap[i][j] = x;

            if (x == 0)
                space.push_back(make_p(i, j));

            if (x == 2)
                virus.push_back(make_p(i, j));
        }
    }

    answer = -1;

    build_wall(0);

    cout << answer << endl;
}