[백준] 14502 연구소 (C++)

문제

14502번: 연구소 (acmicpc.net)

14502번: 연구소

 

풀이

연구소 내 최대 안전구역을 확보하기 위해 3개의 벽을 어떻게 설치할지 결정하는 문제입니다.

 

N x M 의 칸 중 3개를 선택하는 조합(combination)입니다.

다행히도 벽을 꼭 3개를 세워야 하므로 전체 경우의 수는 많지 않습니다. 그렇기 때문에 완전탐색으로 문제를 해결할 수 있습니다.

 

벽을 어떻게 세울지 결정하였다면 그래프 탐색 알고리즘을 이용하여 바이러스가 닿지 않는 안전구역의 칸 수를 확인해주면 됩니다.

 

 

 

완전 탐색

 

연구소의 모양은 2차원 배열로 표현되는데, 구현의 편의를 위해 1차원 배열로 취급하고 인덱스를 부여하겠습니다.

재귀 호출을 이용하여 구현한 combination 입니다.

void setWall (int idx, int cnt, int maxCnt)
{
    if (cnt == maxCnt)
    {
        answer = max(answer, bfs());
        return;
    }

    for (int i=idx; i<n * m; ++i)
    {
        int x = i / m;
        int y = i % m;
        if (board[x][y] != 0)
            continue;

        board[x][y] = 1;
        setWall(i+1, cnt+1, maxCnt);
        board[x][y] = 0;
    }
}

• 1차원 인덱스 : idx = m * x + y, 2차원 인덱스 `x = i / m, y = i % m` 으로 구할 수 있습니다.
• 재귀 호출 깊이를 `cnt` 변수를 이용하여 관리합니다. maxCnt만큼 재귀호출되었다면 `maxCnt` + 1 번째 에서 그래프 탐색을 통해 안전 구역의 개수를 셉니다.
• 재귀호출을 하기 전 벽을 세우고, 호출 후에 다음 조합을 찾기 위해 벽을 지웁니다.

 

그래프 탐색

 

바이러스의 위치를 시작으로 flood fill 을 수행합니다.

안전구역의 수를 확인하기 위해 매 탐색마다 N x M 을 모두 확인 할 수도 있지만,
미리 벽이 아닌 칸 수(`zeroCnt`)를 세어두고 bfs 탐색으로 바이러스가 한칸씩 퍼질 때마다 `zeroCnt`를 줄여주며 탐색이 종료 된 후 그 개수를 확인할 수 있습니다.

 

 

 

코드

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

using namespace std;

vector<pair<int, int>> dir { {0, 1}, {1, 0}, {0,-1}, {-1, 0}};

int max(int a, int b) { return a > b ? a : b; }

int n, m;
vector<vector<int>> board;
vector<pair<int, int>> virus;
int zeroCnt = 0;
int answer = 0;

bool OOB(int x, int y)
{
    return x < 0 || x >= n || y < 0 || y >= m;
}

int bfs()
{   
    int maxZero = zeroCnt - 3;
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    for (pair<int, int> v : virus)
    {
        q.push(v);
        visited[v.first][v.second] = true;
    }

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

        for (auto d : dir)
        {
            int nx = x + d.first;
            int ny = y + d.second;

            if (OOB(nx, ny))
                continue;

            if (board[nx][ny] != 0)
                continue;
            
            if (visited[nx][ny])
                continue;

            visited[nx][ny] = true;
            q.push({nx, ny});
            --maxZero;
        }
    }

    return maxZero;
}

void setWall (int idx, int cnt, int maxCnt)
{
    if (cnt == maxCnt)
    {
        answer = max(answer, bfs());
        return;
    }

    for (int i=idx; i<n * m; ++i)
    {
        int x = i / m;
        int y = i % m;
        if (board[x][y] != 0)
            continue;

        board[x][y] = 1;
        setWall(i+1, cnt+1, maxCnt);
        board[x][y] = 0;
    }
}

int main()
{   
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    cin >> n >> m;
    board.resize(n, vector<int>(m));
    for(int i=0; i<n; ++i)
    {
        for (int j=0; j<m; ++j)
        {
            cin >> board[i][j];

            if (board[i][j] == 2)
            {
                virus.push_back({i, j});            
            }
            else if (board[i][j] == 0)
            {
                ++zeroCnt;
            }
        }
    }

    setWall(0, 0, 3);
    cout << answer << endl;

    return 0;
}