14502번 연구소 G5.py

빈 칸, 벽, 바이러스의 위치 정보가 주어진다.

바이러스가 확산이 되는데 벽을 추가로 3개를 세워서 최대한 확산을 막아야하는 문제다.

조건
연구소의 크기는 최소 3x3 에서 최대 8x8
0은 빈칸, 1은 벽, 2는 바이러스
2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수
빈 칸의 개수는 3개 이상

출력 - 안전 영역의 최대 크기 출력 (바이러스가 확산되지 않은 곳)

이 문제 또한 벽을 세울 수 있는 모든 경우를 다 구해서 해결해야했다.

백트래킹으로 벽을 세울 위치를 정하고 bfs로 바이러스를 확산시켰다.

8x8 크기에서 바이러스가 2군데 있고 나머지 모두 빈칸이라고 해도
62x61x60가지 경우의 벽 세우기와 각 경우마다 bfs 수행

시간은 충분하다 생각해서 구현을 시작했다.

이렇게까지 차이가 나는게 신기하다.
python과 pypy의 차이점에 대한 설명을 찾아봐도 명확히 이해는 되지 않는다.ㅎㅎ

from sys import stdin
from collections import deque

#빈 칸 중에서 3칸을 골라 벽을 세운다
#그리고 바이러스 확산
#바이러스 확산된 범위 저장
#모든 경우 반복

dx = [0, 1, 0, -1]
dy = [1, 0, -1 ,0]

def spread():
    global check, info, spread_result
    visited = [[0 for i in range(m)] for j in range(n)]
    #벽 세울 곳은 미리 방문 처리
    for i in range(len(check)):
        if check[i] == 1:
            visited[info[0][i][0]][info[0][i][1]] = 1

    q = deque()
    for i in info[2]:
        q.append(i)
        visited[i[0]][i[1]] = 1
    cnt = len(info[2])
    while q:
        temp = q.popleft()
        for i in range(4):
            nx = dx[i] + temp[0]
            ny = dy[i] + temp[1]
            if 0<=nx<n and 0<=ny<m and g[nx][ny] == 0 and visited[nx][ny] == 0:
                q.append((nx, ny))
                visited[nx][ny] = 1
                cnt+=1
    spread_result = min(spread_result, cnt)

def build(p, k):
    global check
    if k == 3:
        spread()
        return
    for i in range(p, len(check)):
        if check[i] == 0:
            check[i] = 1
            build(i+1, k+1)
            check[i] = 0

n, m = map(int, stdin.readline().split())
g = [list(map(int, stdin.readline().split())) for i in range(n)]

info = {0:[], 1:[], 2:[]}
#0:빈 칸, 1:벽, 2:바이러스
for i in range(n):
    for j in range(m):
        info[g[i][j]].append((i,j))
check = [0 for i in range(len(info[0]))] #벽 세울 곳 체크
spread_result = 65
build(0, 0)

print(n*m - (len(info[1])+3) - spread_result)