[Baekjoon(백준)][14502번] 연구소(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "연구소" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 바이러스가 있는 연구소에서 벽을 세워 바이러스의 확산을 막고, 안전 영역의 최대 크기를 구하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

14502번: 연구소

문제 개요

"연구소" 문제는 바이러스가 있는 연구소에서 벽을 세워 바이러스의 확산을 막고, 안전 영역의 최대 크기를 구하는 문제입니다. 연구소는 N×M 크기의 직사각형으로 나타내며, 바이러스는 상하좌우 인접한 빈 칸으로 퍼질 수 있습니다.

해결 방법

이 문제는 깊이 우선 탐색(DFS) 알고리즘을 사용하여 해결할 수 있습니다. 벽을 3개 세우는 모든 경우를 시도하고, 각 경우마다 바이러스를 퍼뜨려 안전 영역의 크기를 계산합니다. 이때, 안전 영역의 최대 크기를 구해야 합니다.

코드 구현

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

int n, m;
int maps[12][12];
int visited[12][12];

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

vector<pair<int, int>> virus;
vector<pair<int, int>> wallList;

// 바이러스를 퍼뜨리는 함수
void dfs(int y, int x) {
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
        if (visited[ny][nx]) continue;
        if (maps[ny][nx] == 1) continue;
        visited[ny][nx] = true;
        dfs(ny, nx);
    }
    return;
}

// 안전 영역 크기를 계산하는 함수
int solve() {
    fill(&visited[0][0], &visited[0][0] + 12 * 12, 0);
    for (pair<int, int> b : virus) {
        visited[b.first][b.second] = true;
        dfs(b.first, b.second);
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maps[i][j] == 0 && !visited[i][j]) cnt++;
        }
    }
    return cnt;
}

int main() {
    ios_base::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 >> maps[i][j];
            if (maps[i][j] == 0) wallList.push_back({i, j});
            if (maps[i][j] == 2) virus.push_back({i, j});
        }
    }
    int ret = 0;
    for (int i = 0; i < wallList.size(); i++) {
        for (int y = 0; y < i; y++) {
            for (int x = 0; x < y; x++) {
                maps[wallList[i].first][wallList[i].second] = 1;
                maps[wallList[y].first][wallList[y].second] = 1;
                maps[wallList[x].first][wallList[x].second] = 1;
                ret = max(ret, solve());
                maps[wallList[i].first][wallList[i].second] = 0;
                maps[wallList[y].first][wallList[y].second] = 0;
                maps[wallList[x].first][wallList[x].second] = 0;
            }
        }
    }
    cout << ret << "\n";
}

코드 설명

위 코드는 벽을 세울 수 있는 모든 위치의 조합을 시도합니다. 각 조합에 대해 바이러스를 퍼뜨리고, 안전 영역의 크기를 계산합니다. 계산된 안전 영역의 크기 중 최대값을 구하여 출력합니다.

결론

"연구소" 문제는 깊이 우선 탐색(DFS)과 브루트포스 알고리즘을 결합하여 해결할 수 있습니다. 벽을 세울 수 있는 모든 위치의 조합을 시도하고, 각 경우에 대해 바이러스를 퍼뜨려 안전 영역의 크기를 계산하여 최대값을 구하는 방식으로 해결합니다.