[C++] 백준 - 14502 : 연구소

문제 링크

14502번: 연구소

 

풀이 )

  먼저 완전탐색으로 3개의 벽을 세운다.

  벽을 세운 모든 경우에 대해서 바이러스가 퍼진 지도를 BFS로 구한 뒤 바이러스가 퍼지지 않은 좌표의 수의 최댓값을 구한다.

 

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

using namespace std;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int n, m, ans;
int map[8][8];
queue<int> q;

int spread(void){
    int ret = 0;
    int tmp[8][8];
    memcpy(tmp, map, sizeof(map));
    queue<int> tmpq(q);

    while(!tmpq.empty()){
        int x = tmpq.front()/10;
        int y = tmpq.front()%10;
        tmpq.pop();
        for(int dir = 0; dir < 4; ++dir){
            int xx = x+dx[dir];
            int yy = y+dy[dir];
            if(xx < 0 || xx >= n || yy < 0 || yy >= m)
                continue;
            if(tmp[xx][yy] > 0)
                continue;
            tmp[xx][yy] = 2;
            tmpq.push(xx*10+yy);
        }
    }

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(tmp[i][j] == 0)
                ret++;

    return ret;
}

void wall(int x, int y, int cnt){
    if(cnt == 3){
        ans = max(ans, spread());
        return;
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(map[i][j] == 0){
                map[i][j] = 1;
                wall(i, j, cnt+1);
                map[i][j] = 0;
            }
        }
    }
}

int main(void){
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> map[i][j];
            if(map[i][j] == 2)
                q.push(i*10+j);
        }
    }

    wall(0, 0, 0);
    cout << ans << '\n';
}

 

주의 )

  바이러스가 퍼질 때, 지도와 바이러스의 위치를 담은 queue를 각각 복사해서 사용해야 다음번 시도에 영향을 주지 않는다.