백준 14502번 연구소 (C++)

문제 링크 : https://www.acmicpc.net/problem/14502

14502번: 연구소

이 문제에서 핵심적으로 구현해야하는 요소는 다음 두 가지다.
(1) 벽을 3개 세울 곳
(2) 바이러스가 다 퍼진 후 안전구역의 크기

처음에 벽을 3개 세울 곳을 고민하다보면 자연스럽게 '브루트 포스'가 떠오를텐데, 이렇게되면 시간 초과가 나지 않을까 고민하는 사람도 있을것이다. 하지만 이 문제는 브루트 포스를 활용해도 시간초과가 나지 않는다. 배열의 사이즈는 최대 8*8이기 때문이다.

(1) 벽을 3개 세울 곳 -> 8*8 배열을 3번 거침 -> 64^3
(2) 바이러스가 다 퍼진 후 안전구역의 크기 -> 8*8 배열을 1번 거침 -> 64^1

최대 O(64^4)를 진행하더라도, 계산량의 최대값은 16777216이기 때문에 문제에서 활용하지 못할 정도의 시간초과는 발생하지 않는다.

---

문제 풀이는 다음과 같다.
1. 먼저 필요한 값을 입력 받는다.

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

2. 3번의 연속 2중 for문을 진행한다. 이는 벽 3개를 세울 곳을 지정하기 위함이다.
먼저 아래 코드를 대략적으로 훑어보자.

    for (int y1 = 1; y1 <= n; y1++) { // 1
        for (int x1 = 1; x1 <= m; x1++) {
            if (arr[y1][x1] != 0) continue;
            for (int y2 = 1; y2 <= n; y2++) { // 2
                for (int x2 = 1; x2 <= m; x2++) {
                    if (arr[y2][x2] != 0 || (y1 == y2 && x1 == x2)) continue;
                    for (int y3 = 1; y3 <= n; y3++) { // 3
                        for (int x3 = 1; x3 <= m; x3++) {
                            if (arr[y3][x3] != 0) continue;
                            if (y1 == y3 && x1 == x3) continue;
                            if (y2 == y3 && x2 == x3) continue;
                            arr[y1][x1] = 1; // 4
                            arr[y2][x2] = 1;
                            arr[y3][x3] = 1;
                            cnt = bfs(); // 5
                            if (cnt > ans) ans = cnt; // 6
                            arr[y1][x1] = 0; // 7
                            arr[y2][x2] = 0;
                            arr[y3][x3] = 0;
                        }
                    }
                }
            }
        }
    }

(1) 첫 번째 벽을 세울 장소를 찾아본다. 만약 해당 위치가 0이 아닐 경우, 벽을 세울 수 없으므로 continue한다.
(2) 두 번째 벽을 세울 장소를 찾아본다. 만약 해당 위치가 0이 아닐 경우, 벽을 세울 수 없으므로 continue한다.
동시에 두 번째 벽의 위치와 첫 번째 벽의 위치가 같을 경우, 다른 장소에 세워야 하므로 continue한다.
(3) 세 번째 벽을 세울 장소를 찾아본다. 만약 해당 위치가 0이 아닐 경우, 벽을 세울 수 없으므로 continue한다.
동시에 세 번째 벽의 위치가 첫 번째 벽, 혹은 두 번째 벽의 위치와 같을 경우, 벽을 세울 수 없으므로 continue한다.
(4) 각 위치에 벽을 세워준다.
(5) BFS를 통해 벽을 세우고 난 후 안전구역의 갯수를 판단한다.
(6) (5)번을 통해 구한 안전구역의 갯수가 정답값보다 클 경우, 정답값을 새로 갱신해준다.
(7) 다시 벽을 없앤다.

3. 다음은 코드는 BFS함수이다.

int bfs() {
    int safe = 0;
    queue<pair<int, int>> q; // 1
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            temp[i][j] = arr[i][j];
            if (temp[i][j] == 2) q.push({ i,j });
        }
    }
    while (!q.empty()) { // 2
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) { // 3
            int ny = y + my[i];
            int nx = x + mx[i];
            if (ny >= 1 && ny <= n && nx >= 1 && nx <= m && temp[ny][nx] == 0) {
                temp[ny][nx] = 2;
                q.push({ ny,nx });
            }
        }
    }
    for (int i = 1; i <= n; i++) { // 4
        for (int j = 1; j <= m; j++) {
            if (temp[i][j] == 0) safe++;
        }
    }
    return safe;
}

(1) 배열을 복사해준다. 이때 복사된 배열의 위치 값이 2일 경우, 큐에 해당 위치를 삽입해준다.
(2) 큐가 빌때까지 while문을 진행한다. 큐의 front값을 각 함수에 저장해주고 pop해준다.
(3) 현재 위치를 기점으로 4방향으로 바이러스가 퍼질 수 있는 위치를 판단한다.
만약 4방향의 위치 값이 0이고, 해당 위치가 배열의 범위를 초과하지 않을 경우 해당 위치의 값을 2로 갱신해주고 위치를 큐에 삽입해준다.
(4) while문을 종료하고 배열에서 0의 갯수를 세워준다. 이는 안전한 구역의 갯수이며, 갯수를 모두 세고 안전구역 갯수를 반환해준다.

4. main에서 모든 for문을 종료하고 정답을 출력한다.

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int n, m, arr[9][9], temp[9][9], my[] = { 1,0,-1,0 }, mx[] = { 0,1,0,-1 }, ans, cnt;

int bfs() {
    int safe = 0;
    queue<pair<int, int>> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            temp[i][j] = arr[i][j];
            if (temp[i][j] == 2) q.push({ i,j });
        }
    }
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + my[i];
            int nx = x + mx[i];
            if (ny >= 1 && ny <= n && nx >= 1 && nx <= m && temp[ny][nx] == 0) {
                temp[ny][nx] = 2;
                q.push({ ny,nx });
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (temp[i][j] == 0) safe++;
        }
    }
    return safe;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> arr[i][j];
    }
    for (int y1 = 1; y1 <= n; y1++) {
        for (int x1 = 1; x1 <= m; x1++) {
            if (arr[y1][x1] != 0) continue;
            for (int y2 = 1; y2 <= n; y2++) {
                for (int x2 = 1; x2 <= m; x2++) {
                    if (arr[y2][x2] != 0 || (y1 == y2 && x1 == x2)) continue;
                    for (int y3 = 1; y3 <= n; y3++) {
                        for (int x3 = 1; x3 <= m; x3++) {
                            if (arr[y3][x3] != 0) continue;
                            if (y1 == y3 && x1 == x3) continue;
                            if (y2 == y3 && x2 == x3) continue;
                            arr[y1][x1] = 1;
                            arr[y2][x2] = 1;
                            arr[y3][x3] = 1;
                            cnt = bfs();
                            if (cnt > ans) ans = cnt;
                            arr[y1][x1] = 0;
                            arr[y2][x2] = 0;
                            arr[y3][x3] = 0;
                        }
                    }
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}