[알고리즘 문제] 백준14502 - 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

문제는 완전탐색과 bfs로 풀었습니다. 처음 bfs대신 dfs로 풀어보려고했는데 bfs로 푸는게 더 적절한 문제였습니다. 그렇게 간단한 문제같지는 않습니다.

 

완전탐색으로(재귀) 벽을 세우고, 벽을 3개까지 세웠을 때 바이러스를 퍼뜨려보았습니다(bfs). 그리고 안전구역을 계산해 계속 갱신해 주는 방법으로 문제를 풀었습니다.

 

처음 바이러스를 퍼뜨릴 때 2중 for문안에서 map[y][x]==2 일때 bfs를 구현했습니다. 이렇게 되는 경우 이미 2인 부분을 또 검사해야 하기 때문에 시간을 많이 잡아먹었습니다. 실제로 이런식으로 구현했을 때 1648ms 정도 걸렸습니다.

 

이런 방식말고, 처음 2중 for문에서 map[y][x]의 y,x위치를 que에 모두 넣고 2중 for문을 벗어났을 때 bfs를 하였는데, 이렇게 하면 이미 바이러스인 부분을 다시 검사할 필요가 없었고 시간도 240ms로 줄어들었습니다.

 

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int map[9][9];
int answer = -1;
int height, width;
int dx[4] = {0, 1, 0, -1}; // 상 우 하 좌
int dy[4] = {-1, 0, 1, 0};

void bfs() // 바이러스는 퍼뜨리고, 최대 안정구역 갱신
{

    int virusMap[9][9];

    // 현재 map 상태 복사
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            virusMap[y][x] = map[y][x];
        }
    }

    queue<pair<int, int>> que;

    // 바이러스 위치 저장
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (virusMap[y][x] == 2)
            {
                que.push({y, x});
            }
        }
    }

    // 바이러스 퍼뜨리기
    while (!que.empty())
    {
        pair<int, int> cur = que.front();
        que.pop();

        virusMap[cur.first][cur.second] = 2;
        for (int i = 0; i < 4; i++)
        {
            int newY = cur.first + dy[i];
            int newX = cur.second + dx[i];

            if (newY >= height || newY < 0 || newX >= width || newX < 0) // map의 크기를 벗어나는 경우 예외처리
            {
                continue;
            }
            if (virusMap[newY][newX] == 0)
            {
                virusMap[newY][newX] = 2;
                que.push({newY, newX});
            }
        }
    }

    int safetyZone = 0;

    // 안전한 구역 계산
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (virusMap[y][x] == 0) // 빈공간 체크
            {
                safetyZone++;
            }
        }
    }
    answer = safetyZone > answer ? safetyZone : answer;
}

// 재귀로 벽을 허물고 세울고를 반복
void search(int wall)
{
    if (wall == 3)
    {
        bfs();
        return;
    }
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {

            if (map[y][x] == 0) // 빈공간이면 벽을 세워봄
            {
                map[y][x] = 1;
                search(wall + 1);
                map[y][x] = 0;
            }
        }
    }
}

int main()
{

    cin >> height >> width;

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            cin >> map[y][x];
        }
    }

    search(0);
    cout << answer;
    return 0;
}