백준 14502 연구소 (C++)

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

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

using namespace std;

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

int arr[8][8];
int sim[8][8];

bool visit[8][8];

int n, m;
int ans = 0;
vector<pair<int, int>> virus;

void initSim(){

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sim[i][j] = arr[i][j];
            visit[i][j] = false;
        }
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> n >> m;


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

            if (arr[i][j] == 2) {
                virus.push_back(make_pair(i, j));
            }
        }
    }




    for (int i = 0; i < n * m - 2; i++) {
        for (int j = i + 1; j < n * m - 1; j++) {
            for (int k = j + 1; k < n * m; k++) {

                initSim();

                int wall = 0;
                if (sim[i / m][i % m] == 0) {
                    sim[i / m][i % m] = 1;
                    wall++;
                }
                if (sim[j / m][j % m] == 0) {
                    sim[j / m][j % m] = 1;
                    wall++;
                }
                if (sim[k / m][k % m] == 0) {
                    sim[k / m][k % m] = 1;
                    wall++;
                }

                if (wall == 3) {

                    queue<pair<int, int>> q;

                    for (int vi = 0; vi < virus.size(); vi++) {
                        q.push(virus[vi]);
                    }

                    while (!q.empty()) {

                        pair<int, int> cur = q.front();
                        q.pop();

                        for (int dir = 0; dir < 4; dir++) {
                            int ny = cur.first + dy[dir];
                            int nx = cur.second + dx[dir];

                            if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                                if (!visit[ny][nx] && sim[ny][nx] == 0) {
                                    visit[ny][nx] = true;
                                    sim[ny][nx] = 2;
                                    q.push(make_pair(ny, nx));
                                }

                            }

                        }



                    }

                    int cnt = 0;

                    for (int w = 0; w < n; w++) {
                        for (int h = 0; h < m; h++) {
                            if (sim[w][h] == 0) {
                                cnt++;
                            }
                        }
                    }

                    ans = max(ans, cnt);

                }
            }
        }
    }

    cout << ans;

    return 0;
}

1. 문제

n*m개의 연구소 현황이 주어진다. 0은 빈 공간, 1은 벽, 2는 바이러스이다. 이 연구소의 빈 공간중 정확히 3개를 골라 벽을 설치하려 한다. 이후 바이러스가 퍼지는데, 바이러스는 상하좌우의 빈 공간에 퍼진다. 다 퍼진 후 빈 공간을 안전 공간이라 칭하고, 이 넓이를 최대로 하려 할 때, 그 넓이를 출력하라.

2. 풀이

정확히 3개의 벽을 임의의 공간에 설치하고, 공간은 최대 8*8이므로 브루트포스를 이용하여 풀 수 있다.

    int arr[8][8];
    int sim[8][8];


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

            if (arr[i][j] == 2) {
                virus.push_back(make_pair(i, j));
            }
        }
    }

연구소 현황을 입력받는다. 처음 연구소 현황을 유지해야 하므로 sim이라는 배열을 만든다. 이 배열에 벽을 설치하고, 바이러스를 퍼뜨릴 것이다. 바이러스를 퍼뜨릴 위치가 필요하므로 저장해준다.

    for (int i = 0; i < n * m - 2; i++) {
        for (int j = i + 1; j < n * m - 1; j++) {
            for (int k = j + 1; k < n * m; k++) {

                initSim();

                int wall = 0;
                if (sim[i / m][i % m] == 0) {
                    sim[i / m][i % m] = 1;
                    wall++;
                }
                if (sim[j / m][j % m] == 0) {
                    sim[j / m][j % m] = 1;
                    wall++;
                }
                if (sim[k / m][k % m] == 0) {
                    sim[k / m][k % m] = 1;
                    wall++;
                }

이후 모든 연구소를 돌며 3개의 빈공간을 찾는다면 벽을 세운다.

,

 if (wall == 3) {

                    queue<pair<int, int>> q;

                    for (int vi = 0; vi < virus.size(); vi++) {
                        q.push(virus[vi]);
                    }

                    while (!q.empty()) {

                        pair<int, int> cur = q.front();
                        q.pop();

                        for (int dir = 0; dir < 4; dir++) {
                            int ny = cur.first + dy[dir];
                            int nx = cur.second + dx[dir];

                            if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                                if (!visit[ny][nx] && sim[ny][nx] == 0) {
                                    visit[ny][nx] = true;
                                    sim[ny][nx] = 2;
                                    q.push(make_pair(ny, nx));
                                }

                            }

                        }

벽이 3개라면 각 바이러스의 시작점에 대해 BFS를 돌린다. 다음 위치가 방문하지 않은 빈 공간일 경우 해당 위치에 바이러스를 퍼뜨리고, 다음 탐색위치로 저장해준다.

  int cnt = 0;

                    for (int w = 0; w < n; w++) {
                        for (int h = 0; h < m; h++) {
                            if (sim[w][h] == 0) {
                                cnt++;
                            }
                        }
                    }

                    ans = max(ans, cnt);

모든 바이러스를 퍼뜨린 후, 연구소를 순회하면서 빈 공간(안전 공간)의 개수를 세어주고, 그 최댓값을 갱신해준다.

 

연산이 끝나고 ans를 출력하면 정답을 구할 수 있다.