[14502] 연구소

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

14502번: 연구소

<문제>

결론적으론 브루트포스, 시간내에 해결할 수 있는지 생각해보자.

맵의 최대크기는 8*8, 64칸이다.

여기에 빈칸중 일부를 선택해서 벽을 세워야 하므로, 빈칸의 최대개수도 구해봐야한다.

빈칸의 최대개수는 64-2(바이러스의 최소개수) = 62개이다.

이중 3개를 선택하면, (62*61*60) / 3! 이다.

대략 60*60*10=36000번 정도의 연산횟수로 벽을 세울 수 있다.

벽을 세울 수 있는 경우의 수는 36000, 여기에 한번의 바이러스의 확산에 필요한 연산횟수는 O(N*M)정도이다.

하나의 칸마다 인접한 칸 모두를 참조하므로, 실제 연산횟수는 O(4*N*M)정도로 생각되지만, 그래봤자 250번 정도다.

문제의 제한시간은 2초, 36000 * 250 < 2억 이므로, 브루트포스로 충분히 해결할 수 있는 문제다.

---

로직은 이러하다.

1. 빈칸중 3개를 선택하는 모든 조합을 만들어보며, 선택된 칸3개에 벽을 세운다.

2. 세워진 벽을 바탕으로 바이러스의 확산을 진행한다. 이는 dfs, bfs등을 적용하는 부분이다.

3. 확산이 진행 된 이후, 안전구역의 개수를 계산하고 이를 바탕으로 정답(최대값)을 업데이트한다.

 

1에서 2로 거치는 과정중, 원래 입력된 맵을 잃으면 안되기 때문에 맵의 복사본을 만들어서 (2)를 수행하는 등,

맵을 copy하는 과정이 필요하다.

 

 

<소스코드>

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
int a[10][10], input[10][10];
int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
bool check[70], visit[10][10];
int n, m, answer;
vector <pair<int, int>>zero;
vector <pair<int, int>>bfs_start;
queue<int>q;
void bfs(int sy, int sx);
 
void Init(void) {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            a[i][j] = input[i][j];
        }
    }
    return;
}
void makeWall(int depth, int idx) {
    int i, j, len, y, x, score;
    if (depth == 3) {
        Init();
        for (i = 0; i < bfs_start.size(); i++) {
            y = bfs_start[i].first;
            x = bfs_start[i].second;
            bfs(y, x);
        }
        score = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < m; j++) {
                if (a[i][j] == 0) {
                    score++;
                }
            }
        }
        answer = max(score, answer);
        return;
    }
    for (i = idx; i < zero.size(); i++) {
        if (check[i] == false) {
            check[i] = true;
            makeWall(depth + 1, i+1);
            check[i] = false;
        }
    }
    return;
}
void bfs(int sy, int sx) {
    int ty, tx, y, x, i;
    q.push(sy);
    q.push(sx);
    memset(visit, false, sizeof(visit));
    visit[sy][sx] = true;
    for (i = 0; i < zero.size(); i++) {
        if (check[i] == true) {
            y = zero[i].first;
            x = zero[i].second;
            a[y][x] = 1;
        }
    }
    while (!q.empty()) {
        ty = q.front();
        q.pop();
        tx = q.front();
        q.pop();
        for (i = 0; i < 4; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m)continue;
            if (visit[y][x] == false && a[y][x] == 0) {
                q.push(y);
                q.push(x);
                visit[y][x] = true;
                a[y][x] = 2;
            }
        }
    }
}
int main(void) {
    int i, j;
    scanf("%d %d", &n, &m);
    memset(visit, false, sizeof(visit));
    memset(check, false, sizeof(check));
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%d", &input[i][j]);
            if (input[i][j] == 0) {
                zero.push_back(make_pair(i, j));
            }
            else if (input[i][j] == 2) {
                bfs_start.push_back(make_pair(i, j));
            }
        }
    }
    makeWall(0, 0);
    printf("%d", answer);
    return 0;
}