백준 / python / 14502. 연구소

https://www.acmicpc.net/problem/14502

 

문제 요약

NxM 크기의 연구소에 2 로 표현되는 바이러스와 1로 표현되는 벽이 있다. 벽을 3개 더 세워서 바이러스가 최대한 적은 공간에 퍼지게 했을 때, 바이러스가 없는 공간의 크기를 구하라.

 

 

풀이 요약

1. N, M 이 8까지이고 세워야하는 벽의 수는 3개이다. 따라서 총 $ \binom{N*M}{3} = 41,664 $ 번의 bfs / dfs 를 수행하면 된다.
2. bfs / dfs 의 시간복잡도는 $ O(V + E) = O(N * M + (M-1)*N+(N-1)*M) = O(N*M)$ 이므로 1초 안에 수행 가능하다. 
3. 그러므로 브루트 포스로 빈 공간에 벽을 세우고 bfs / dfs 를 실행하여 안전한 공간의 수를 구하는 것을 반복한다.

 

주의사항

1. bfs 보다 dfs 가 400ms 정도 빠르다.
   재귀로 구현하지 않아서 bfs 와 동일한 메모리를 사용하나 deque 대신 기본 list 를 사용하기 때문에 성능이 좋은 것 같다.
   그리고 bfs에서 경로가 겹치는 경우가 빈번해서 느린 것 같다.
2. 방문여부를 체크하는 용도의 변수는 dict < set < list 순으로 성능이 좋았다.

from sys import stdin
from itertools import combinations

input = stdin.readline

N, M = map(int, input().split())
graph = []
moves = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
]

pos_empty = []
pos_twos = []
for n in range(N):
    row = [*map(int, input().split())]
    for m in range(M):
        if row[m] == 0:
            pos_empty.append((n, m))
        elif row[m] == 2:
            pos_twos.append((n, m))

    graph.append(row)


def dfs():
    q = pos_twos[:]
    visited = [False] * (M * N)
    cnt = 0
    while q:
        y, x = q.pop()
        for dy, dx in moves:
            ny = y + dy
            nx = x + dx

            if (
                0 <= ny < N
                and 0 <= nx < M
                and graph[ny][nx] == 0
                and not visited[nx + ny * M]
            ):
                visited[nx + ny * M] = True  # set 과 dict 과 list 성능차이 ?
                cnt += 1
                if cnt > min_cnt_twos:
                    return 100

                q.append((ny, nx))
    return cnt


min_cnt_twos = 100
for comb in combinations(pos_empty, 3):
    for y, x in comb:
        graph[y][x] = 1

    temp = dfs()
    if min_cnt_twos > temp:
        min_cnt_twos = temp

    for y, x in comb:
        graph[y][x] = 0

print(len(pos_empty) - 3 - min_cnt_twos)