BOJ - 14502 연구소

14502번 연구소

주어진 연구소에 벽 3개를 세워 바이러스의 확산을 최소화 하여 안전구역을 최대한으로 하는 것이 주어진 문제이다.

bfs를 사용하여 바이러스의 확산된 구역을 구하면 풀리는 문제이다.

하지만 단순히 bfs를 적용하는 것이 아니라 주어진 연구소의 빈 부분에 벽 세개를 세우는 모든 경우에 대해 시행하여야 한다.

문제 해결 순서는 다음과 같다.

1. 바이러스의 시작 지점을 저장한다.(bfs의 시작 지점으로 설정해 주기 위해)
2. 연구소의 빈 공간에 벽 3개를 세운다.
3. 벽을 세운 연구소에 대해 bfs를 적용한다.
4. bfs를 적용 할 때 저장 되어 있던 바이러스의 시작 지점에 대해 진행한다.
5. 방문 여부를 저장한 배열을 통해 안전 구역의 갯수를 구한다.
6. 1~5를 반복하며 최대 안전 구역의 갯수를 구한다.

문제 해결 과정에서 사용된 알고리즘은 bfs이다.

코드

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

using namespace std;
int visited[9][9];
int arr[9][9];
int wall;
int n,m;
int xpos[4] = {-1,0,1,0};
int ypos[4] = {0,1,0,-1};
vector<pair<int,int>> v;

int bfs()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(arr[i][j] == 1)
                visited[i][j] = 1;
            else
                visited[i][j] = 0;
        }
    }

    queue<pair<int,int>> q;

    for(int i=0;i<v.size();i++)
    {
        q.push(make_pair(v[i].first, v[i].second));
    }

    while(!q.empty())
    {
        int x,y;
        x = q.front().first;
        y = q.front().second;
        q.pop();


        if(visited[x][y] != 0)
            continue;

        visited[x][y] = 2;

        for(int i=0;i<4;i++)
        {
            if(x+xpos[i] < 0 || x+xpos[i] >= n || y+ypos[i] < 0 || y+ypos[i] >= m)
                continue;

            if(arr[x+xpos[i]][y+ypos[i]] == 1) {
                continue;
            }

            if(visited[x+xpos[i]][y+ypos[i]] !=0)
                continue;

            q.push(make_pair(x+xpos[i],y+ypos[i]));
        }
    }

    int count = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(visited[i][j] == 0)
                count++;
        }
    }
    return count;
}

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

    cin >> n >> m;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin >> arr[i][j];

            if(arr[i][j] == 2)
                v.push_back(make_pair(i,j));
        }
    }

    /* 빈 공간에 벽 세우기 */
    int max = 0;
    for(int i=0;i<n*m-2;i++)
    {
        if(arr[i/m][i%m] != 0)
            continue;

        for(int j=i+1;j<n*m-1;j++)
        {
            if(arr[j/m][j%m] != 0)
                continue;

            for(int k=j+1;k<n*m;k++)
            {
                if(arr[k/m][k%m] != 0)
                    continue;

		/* 조건에 부합하면 벽 세우기 */
                arr[i/m][i%m] = 1;
                arr[j/m][j%m] = 1;
                arr[k/m][k%m] = 1;

                int tmp = bfs();
                if(tmp > max) {
                    max = tmp;
                }
                
         	/* bfs 적용 후 다시 연구소 원상 복구 시키기 */
                arr[i/m][i%m] = 0;
                arr[j/m][j%m] = 0;
                arr[k/m][k%m] = 0;
            }
        }
    }

    cout << max;

    return 0;
}

출처 : https://www.acmicpc.net/problem/1946