반응형
알고리즘 분류 : 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)
참고
반응형