프로그래밍/알고리즘

BOJ 17141 · 연구소 2

반응형


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


연구소에 바이러스를 퍼트리는 데 걸리는 최소 시간을 구하는 문제다. 바이러스를 놓을 수 있는 경우를 모두 만든 후, 각 케이스에 대해 BFS로 바이러스를 퍼트려서 최솟값을 구하면 된다.


  • 연구소의 사이즈는 N이며, 바이러스의 개수는 M이다.
  • 바이러스를 놓을 수 있는 칸(2)의 좌표를 별도의 리스트 V에 저장한다.
  • 빈칸(0)의 개수를 모두 세고, 여기에 바이러스를 놓을 수 있는 칸(2)의 개수를 더한 후, M을 뺀다. 이 값은 바이러스를 퍼트려야 하는 칸의 총개수가 된다. 이를 K라 하자.
  • 조합(combination) 방법을 통해 M개의 바이러스를 바이러스 칸(2)에 둔다. 이때 리스트 V를 활용하여, 바이러스를 놓은 칸의 좌표를 큐에 모두 집어넣는다.
  • BFS를 통해 바이러스를 감염시킨다. 감염시킬 때마다, 감염시킨 칸의 개수를 세고, 감염 시간을 계속 업데이트한다.
  • 감염시킬 수 있는 곳은 벽(1)을 제외한 모든 곳이다.
  • BFS가 종료된 후, 감염시킨 칸의 개수와 K가 같은지 비교한다. 만약 비교한 값이 같고, 걸린 시간이 최솟값이라면, 정답으로 업데이트한다.
  • 모든 경우의 수에 대해서 BFS를 수행한다.





C++ 소스코드


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

struct virus {
    int x, y;
};

int a[50][50], dist[50][50];
int n, m, k, ans=1e9;
bool select[10];
vector<virus> v;
queue<virus> q;
const int dx[] = {-1, 0 , 1, 0}, dy[] = {0, 1, 0, -1};

void bfs() {
    int infect=0, times=0;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        times = dist[x][y];
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (a[nx][ny] != 1 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y]+1;
                q.push({nx, ny});
                infect += 1;
            }
        }
    }
    if (infect == k && ans > times) ans = times;
}

void solve(int idx, int cnt, int d) {
    if (cnt == m) {
        memset(dist, -1, sizeof(dist));
        for (int i=0; i<d; i++) {
            if (select[i]) {
                q.push({v[i].x, v[i].y});
                dist[v[i].x][v[i].y] = 0;
            }
        }
        bfs();
        return;
    }
    for (int i=idx; i<d; i++) {
        if (!select[i]) {
            select[i] = true;
            solve(i+1, cnt+1, d);
            select[i] = false;
        }
    }
}

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




Python 3 소스코드


from collections import deque

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
select = [False] * 10
q, v, k = deque(), [], 0

def bfs(dist):
    global ans
    infect, times = 0, 0
    while q:
        x, y = q.popleft()
        times = dist[x][y]
        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 >= n:
                continue
            if a[nx][ny] != 1 and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y]+1
                q.append((nx, ny))
                infect += 1
    if infect == k:
        ans = min(ans, times)

def solve(idx, cnt, d):
    if cnt == m:
        dist = [[-1]*n for _ in range(n)]
        for i in range(d):
            if select[i]:
                x, y = v[i]
                q.append((x, y))
                dist[x][y] = 0
        bfs(dist)
        return
    for i in range(idx, d):
        if not select[i]:
            select[i] = True
            solve(i+1, cnt+1, d)
            select[i] = False

for i in range(n):
    for j in range(n):
        if a[i][j] == 2:
            v.append((i, j))
        if a[i][j] == 0:
            k += 1
ans = 10**9
k = k+len(v)-m
solve(0, 0, len(v))
print(ans if ans != 10**9 else -1)




참고




반응형