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

14502번: 연구소

 solved.ac 클래스 4에 있는 문제이다. 문제를 읽으면서 새로 세울 수 있는 벽은 3개이고, 꼭 3개를 세워야 한다는 것을 보고 브루트포스를 통해 모든 경우를 봐야겠다고 생각했다. 벽을 3개만 세우는 경우의 수가 크지 않기 때문이다. 그 이후에는 바이러스가 퍼지게 되면 차지하는 넓이를 구해주었다. 모든 경우에 대해서 해당 작업을 한 뒤, 빈칸의 개수의 최댓값이 답이다.

 

 

 참고로, '[BOJ] 22953 도도의 음식준비' 문제와 비슷하다고 느꼈다. 22953번 도도의 음식 준비 문제도 C값이 5 이하이기 때문에 모든 경우를 보는 것이 어렵지 않았기 때문이다. 다른 점이라면, 22953번 문제는 (브루트포스+이분탐색)이고, 14502 연구소 문제는 (브루트포스+DFS)이다.

 

---

풀이

 우선, board에 연구소의 상태를 입력받는다. 이 때, 벽이 아닌 곳의 넓이(nowwall)를 계산해준다. 그 후에, solve함수에서 브루트포스 기법을 통해 모든 경우를 다 본다. 이 때, 벽을 3개 세우게 되므로 notwall 값은 3이 줄어든다. solve함수의 input값은 앞으로 설치해야 할 벽의 개수이다. 그 값이 0이면 벽을 모두 설치했다는 의미이다. 

 

벽을 모두 설치하였다면 dfs를 통해 문제를 해결한다. 전체 board를 탐색하면서 바이러스가 있는 곳이면 그 곳을 포함하여 dfs를 통해 바이러스가 퍼진 뒤의 넓이(virus)를 구한다. 그러면 (notwall-virus) 값이 안전한 영역의 넓이가 된다. (벽이 아닌 곳의 넓이 중 바이러스가 있는 넓이를 빼주었으므로)

 

이렇게 구한 notwall-virus값 중 가장 큰 값이 답이 된다.

 

---

코드

#include <iostream>
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

ll n, m, notwall = 0, virus = 0; //notwall은 벽이 아닌 곳의 넓이,virus는 바이러스가 있는 곳의 넓이
ll board[9][9];
ll visited[9][9];
ll dx[4] = { 0,1,0,-1 };
ll dy[4] = { 1,0,-1,0 };
ll ans = -1;

void dfs(ll x, ll y) {
    for (ll i = 0; i < 4; i++) {
        ll nx = x + dx[i];
        ll ny = y + dy[i];
        if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && !visited[nx][ny]) {
            if (board[nx][ny] == 0) {
                virus++;
                visited[nx][ny] = 1;
                dfs(nx, ny);
            }
        }
    }
}

void solve(ll wall) { //wall값은 앞으로 설치해야 할 벽의 개수
    if (wall == 0) {//벽 3개를 모두 설치한 경우
        memset(visited, 0, sizeof(visited)); //dfs하기 전, visited함수 0으로 초기화
        virus = 0;
        for (ll i = 1; i <= n; i++) {
            for (ll j = 1; j <= m; j++) {
                if (board[i][j] == 2 && !visited[i][j]) {
                    virus++;
                    dfs(i, j); //dfs를 통해 바이러스 퍼뜨리는 과정
                }
            }
        }
        ans = max(ans, notwall - virus);
        return;
    }
    else {//아직 벽을 3개 다 설치하지 못한 경우
        for (ll i = 1; i <= n; i++) {
            for (ll j = 1; j <= m; j++) {
                if (board[i][j] == 0) {
                    board[i][j] = 1; //빈칸이면 벽을 설치한다.
                    solve(wall - 1); //벽을 설치했으므로 cnt값을 1 줄여서 solve함수에 넣는다.
                    board[i][j] = 0; //벽을 다시 제거해준다.
                }
            }
        }
    }
}

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

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= m; j++) {
            cin >> board[i][j];
            if (board[i][j] != 1) notwall++; //벽이 아닌 영역의 넓이 계산
        }
    }

    notwall -= 3; //벽을 3개 세워야 하므로 3빼준다.
    solve(3); //벽을 3개 세워야 한다.

    cout << ans << endl;

    return 0;
}