백준 14502. 연구소 (조합, 구현)

https://www.acmicpc.net/problem/14502

14502번: 연구소

벽을 세울 수 있는 위치 3곳 찾고(조합), 이 위치에 벽을 두었을 때 안전구역의 범위를 bfs로 세면 된다. 

이 문제는 전형적이라서 어렵지는 않은데, 시간 복잡도 계산을 한번쯤은 해야 될 거같아서 블로그에 작성한다

 

1. 특징

1) 조합

2) 구현

 

2. 시간 복잡도 계산

조합: 62C3 (n,m이 최대 8이므로 64칸 - 바이러스 최소 2칸 = 62)

bfs: n*m = 64

따라서 대략적으로 2,420,480 연산함. 

시간제한 1초는 대략 1억번 연산이므로 시간제한에 걸리지 않는다.  

 

3. 코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int n, m;
int board[10][10];
int input[10][10];
vector<pair<int, int>> _vec; //바이러스 
vector<pair<int, int>> _emvec; //빈공간 

int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int emptysize; 
int mask[65];
int mx;

//조합 -> bfs
void bfs()
{
    //초기 바이러스를 큐에 넣기
    queue<pair<int, int>> _tmpvec;
    for(int i = 0; i < _vec.size(); i++)
    {
        _tmpvec.push(make_pair(_vec[i].first, _vec[i].second));
    }

    while(!_tmpvec.empty())
    {
        int curx = _tmpvec.front().first;
        int cury = _tmpvec.front().second;
        _tmpvec.pop();

        for(int dir = 0; dir < 4; dir++)
        {
            int nx = curx + dx[dir];
            int ny = cury + dy[dir];

            if(nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1) continue;
            if(board[nx][ny] != 0 ) continue;
            board[nx][ny] = 2;
            _tmpvec.push(make_pair(nx, ny));
        }
    }

    //mx 업데이트
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(board[i][j] == 0) cnt++;
        }
    }

    mx = max(mx, cnt);


}

int main()
{
    cin >> n >> m;

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

            if(x == 2) { _vec.push_back(make_pair(i, j));}
            if(x == 0) { _emvec.push_back(make_pair(i, j)); }
        }
    }

    emptysize = _emvec.size();

    //emptysize 에서 3개 고를거임 {0,0,0,1,1,1,1,1,1,,1,1...}
    for(int i = 3; i < emptysize; i++)
    {
        mask[i] = 1;
    }

    do
    {
        //보드 초기화
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                board[i][j] = input[i][j];

            }
        }

        //선택된 3개의 위치에 벽을 세움.
        for(int i = 0; i < emptysize; i++)
        {
            if(mask[i] == 0)
            {
                int curx = _emvec[i].first;
                int cury = _emvec[i].second;

                board[curx][cury] = 1;
            }

            
        }
        bfs();

    }while(next_permutation(mask, mask + emptysize));

    cout << mx;
}