바이러스

In [1]:

import sys
sys.path.append("/home/swyoo/algorithm/")
from sys import stdin
from copy import deepcopy
from utils.generator import random2D
from utils.verbose import logging_time
import numpy as np

14502.연구소

A virus (which is represented by 2) can be propagated by up, donw, left, right directions as 2.
We have to install 3 walls (which is represented by 1) at empty spaces.
How can we find optimal points for minimizing the dissemination of viruses.

In [2]:

plot = lambda a: print(np.array(a))
stdin = open('data/virus.txt')
input = stdin.readline
n, m = list(map(int, input().split()))
grid = [list(map(int, input().split())) for _ in range(n)]
plot(grid)

[[0 0 0 0 0 0]
 [1 0 0 0 0 2]
 [1 1 1 0 0 2]
 [0 0 0 0 0 2]]

Enumeration of Walls + DFS

This is simple approach. The idea is as follows.
First, enumerate walls. Second, for each stored 3 walls, spread viruses.
Finally, calculate remaining spaces as |mn| - (|1's| + |2's|) = |0's|.

The time complexity analysis as follows.

1. Enumerate walls: ${mn \choose 3} = O((mn)^3)$
2. DFS for spreading viruses: $O(mn)$

Therefore, $O((mn)^4)$. it is a slow algorithm.

In [3]:

@logging_time
def solution(grid, show=False):

    def spread(grid):
        cnt, seen = 0, set()

        def dfs(i, j):
            seen.add((i, j))
            for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and not grid[x][y] and (x, y) not in seen:
                    dfs(x, y)

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1: cnt += 1
                if grid[i][j] == 2 and (i, j) not in seen:
                    dfs(i, j)
        return n * m - (len(seen) + cnt), seen

    ans = 0
    snapshot = None
    spaces = [(i, j) for i in range(len(grid)) for j in range(len(grid[0])) if not grid[i][j]]
    for i in range(len(spaces)):
        for j in range(i + 1, len(spaces)):
            for k in range(j + 1, len(spaces)):
                wi, wj, wk = spaces[i], spaces[j], spaces[k]
                grid[wi[0]][wi[1]] = grid[wj[0]][wj[1]] = grid[wk[0]][wk[1]] = 1
                tmp, seen = spread(grid)
                if tmp > ans:
                    ans = tmp
                    if show:
                        snapshot = deepcopy(grid)
                        for x, y in seen:
                            snapshot[x][y] = 2
                grid[wi[0]][wi[1]] = grid[wj[0]][wj[1]] = grid[wk[0]][wk[1]] = 0
    if show: plot(snapshot)
    return ans

print(solution(grid, show=True, verbose=True))

[[0 0 0 0 1 2]
 [1 0 0 1 2 2]
 [1 1 1 2 2 2]
 [0 0 0 1 2 2]]
WorkingTime[solution]: 19.07587 ms
9

Generate Test Data

In [4]:

n =  m =  10
grid = random2D(shape=(n, m), sampling=[0, 1, 2], weights=[0.7, 0.2, 0.1])
plot(grid)

[[0 0 1 1 0 0 0 0 2 0]
 [0 0 0 1 2 2 0 0 0 1]
 [2 0 1 0 0 2 0 0 1 0]
 [0 1 0 1 0 2 0 0 1 0]
 [2 0 0 0 0 0 1 0 0 0]
 [0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 1 0 0]
 [0 0 0 0 1 0 0 0 0 0]
 [0 0 0 0 2 1 0 2 1 0]
 [0 0 0 0 0 2 0 0 0 2]]

In [5]:

solution(grid, show=True, verbose=True)

[[0 0 1 1 2 2 2 2 2 2]
 [1 0 0 1 2 2 2 2 2 1]
 [2 1 1 2 2 2 2 2 1 0]
 [2 1 2 1 2 2 2 2 1 0]
 [2 2 2 2 2 2 1 2 1 0]
 [2 2 2 2 2 2 2 2 2 1]
 [1 2 2 2 2 2 2 1 2 2]
 [2 2 2 2 1 2 2 2 2 2]
 [2 2 2 2 2 1 2 2 1 2]
 [2 2 2 2 2 2 2 2 2 2]]
WorkingTime[solution]: 8551.43666 ms

7

In [6]:

solution(grid, verbose=True)

WorkingTime[solution]: 8439.22687 ms

7