BOJ 14502 · 연구소

알고리즘 분류 : 브루트 포스, DFS  

연구소에 벽을 3개 세워서 바이러스를 최대한 덜 퍼트리고, 안전 영역의 최대 크기를 구하는 문제다. N*M은 최대 64이므로, 벽을 두는 모든 경우의 수를 구해서 최대 크기를 확인해 볼 수 있다.

• 우선 입력으로 받은 맵에 벽을 3개 세워야 한다.
• 벽(1)은 빈 칸(0)에만 세울 수 있다. N*M을 순회하면서 빈 칸이라면 벽을 둔다.
• 벽을 두는 함수는 재귀로 구현한다. 벽 카운트를 세면서 3이 되면, DFS를 통해 빈 칸에 바이러스(2)를 퍼트린다.
• 바이러스를 퍼트리면서, 바이러스가 퍼진 칸을 센다.
• 바이러스 칸이 최소가 될 때, 안전 영역의 크기가 최대가 된다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int n, m, safe=-3, virus=1e9;
int a[8][8];
bool c[8][8];
vector<pair<int, int>> v;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int dfs(int x, int y) {
    int res = 1;
    c[x][y] = true;
    for (int i=0; i<4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (c[nx][ny] || a[nx][ny]) continue;
        res += dfs(nx, ny);
    }
    return res;
}

void solve(int wall, int x, int y) {
    if (wall == 3) {
        int cnt = 0;
        memset(c, 0, sizeof(c));
        for (auto k : v) {
            cnt += dfs(k.first, k.second);
        }
        if (virus > cnt) virus = cnt;
        return;
    }
    for (int i=x; i<n; i++) {
        int k = i == x ? y : 0;
        for (int j=k; j<m; j++) {
            if (a[i][j] == 0) {
                a[i][j] = 1;
                solve(wall+1, i, j+1);
                a[i][j] = 0;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] != 1) safe++;
            if (a[i][j] == 2) v.push_back({i, j});
        }
    }
    solve(0, 0, 0);
    printf("%d\n", safe-virus);
    return 0;
}

---

Python 3 소스코드

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
c = [[False]*m for _ in range(n)]
v, safe, virus = [], -3, 100

def dfs(x, y):
    res = 1
    c[x][y] = True
    for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
        nx, ny = x+dx, y+dy
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if not (c[nx][ny] or a[nx][ny]):
            res += dfs(nx, ny)
    return res

def solve(wall, x, y):
    global virus, c
    if wall == 3:
        cnt = 0
        c = [[False]*m for _ in range(n)]
        for i, j in v:
            cnt += dfs(i, j)
        virus = min(virus, cnt)
        return
    for i in range(x, n):
        k = y if i == x else 0
        for j in range(k, m):
            if a[i][j] == 0:
                a[i][j] = 1
                solve(wall+1, i, j+1)
                a[i][j] = 0

for i in range(n):
    for j in range(m):
        if a[i][j] != 1:
            safe += 1
        if a[i][j] == 2:
            v.append((i, j))
solve(0, 0, 0)
print(safe-virus)

---

참고

• 백준 온라인 저지 : BOJ 14502