백준 14502번 [연구소](C++)-yes6686- 티스토리

백준 문제 풀이: 14502 [연구소]

---

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

문제 설명:

연구소에서 바이러스가 퍼지는 것을 막기 위해, 벽 3개를 세울 때 안전 영역의 최대 크기를 구하는 문제입니다. 연구소는 n × m 크기의 직사각형으로 주어지며, 각 칸은 다음 중 하나를 나타냅니다:

• 0: 빈 칸
• 1: 벽
• 2: 바이러스가 있는 위치

벽 3개를 세운 후 바이러스가 퍼지는 시뮬레이션을 수행하여, 안전 영역(빈 칸)의 최대 크기를 출력해야 합니다.

입력:

• 첫째 줄에 연구소의 크기 n (3 ≤ n, m ≤ 8)이 주어집니다.
• 다음 n개의 줄에는 연구소의 상태가 주어집니다.

출력:

• 벽 3개를 세운 후 안전 영역의 최대 크기를 출력합니다.

---

문제 해결 코드

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

int n, m;
int lab[8][8];
int temp[8][8];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void spreadVirus() {
    queue<pair<int, int>> q;

    // 바이러스 위치를 큐에 삽입
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            temp[i][j] = lab[i][j];
            if (lab[i][j] == 2) {
                q.push({i, j});
            }
        }
    }

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (temp[nx][ny] == 0) {
                    temp[nx][ny] = 2;
                    q.push({nx, ny});
                }
            }
        }
    }
}

int calculateSafeArea() {
    int safeArea = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (temp[i][j] == 0) {
                safeArea++;
            }
        }
    }
    return safeArea;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    vector<pair<int, int>> emptySpaces;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> lab[i][j];
            if (lab[i][j] == 0) {
                emptySpaces.push_back({i, j});
            }
        }
    }

    int maxSafeArea = 0;

    // 벽 3개를 선택하는 모든 조합
    int size = emptySpaces.size();
    for (int i = 0; i < size - 2; i++) {
        for (int j = i + 1; j < size - 1; j++) {
            for (int k = j + 1; k < size; k++) {
                lab[emptySpaces[i].first][emptySpaces[i].second] = 1;
                lab[emptySpaces[j].first][emptySpaces[j].second] = 1;
                lab[emptySpaces[k].first][emptySpaces[k].second] = 1;

                spreadVirus();
                maxSafeArea = max(maxSafeArea, calculateSafeArea());

                lab[emptySpaces[i].first][emptySpaces[i].second] = 0;
                lab[emptySpaces[j].first][emptySpaces[j].second] = 0;
                lab[emptySpaces[k].first][emptySpaces[k].second] = 0;
            }
        }
    }

    cout << maxSafeArea << '\n';

    return 0;
}

예제

입력:
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

출력:
27

---

코드 설명

• 벽 3개 조합 선택:
  • 빈 공간 좌표를 저장한 후, 세 개의 벽을 세우는 모든 조합을 탐색합니다.
• 바이러스 퍼뜨리기:
  • BFS를 사용하여 바이러스가 퍼지는 과정을 시뮬레이션합니다.
• 안전 영역 계산:
  • 시뮬레이션 후 남아 있는 빈 칸의 개수를 계산하여 최대 안전 영역 크기를 갱신합니다.

시간 복잡도

• 빈 칸의 개수를 e라 할 때, 벽을 세우는 조합의 수는 O(e³)입니다.
• 각 조합에서 BFS를 수행하므로 O(n × m)의 복잡도가 추가됩니다.
• 전체 시간 복잡도: O(e³ × n × m)

---

결과

코드는 연구소의 최대 안전 영역을 정확히 계산하며, 벽 조합과 바이러스 퍼짐 시뮬레이션을 효율적으로 처리합니다. 문제의 제약 조건에 적합한 성능을 보장합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!