백준 14502 "연구소" by 파이썬

문제요약

벽을 무조건 3개 세운 후 바이러스를 퍼뜨린다.
바이러스가 퍼진 후 안전한 영역이 최대일때를 구하여라.

문제해결전략

1. 0인 지역 중 3개를 뽑아 1(=벽)으로 바꾼다.
2. 2(=바이러스)를 퍼뜨린다.
3. 0인 지역 수를 센다.

코드

바이러스를 퍼뜨릴 때 쓸 deque
연구소 상태를 초기화하기 위해 필요한 copy
벽 세울 수 있는 곳 3군데를 뽑기 위해 필요한 combinations

from collections import deque
import copy
from itertools import combinations

연구소 크기를 받을 N,M
연구소 상태를 받을 lab

N, M = map(int, input().split())
lab = [list(map(int,input().split())) for _ in range(N)]

벽 세울 수 있는 곳을 받을 avail
avail 중 3개씩 뽑는 걸 받을 wall

avail = []
for i in range(N):
    for j in range(M):
        if lab[i][j] == 0:
            avail.append((i,j))
            
wall = list(combinations(avail, 3))

바이러스가 퍼질 때 상하좌우로 퍼지니까 dx, dy를 설정
답이 될 ans는 -1로 초기화해둔다. (0으로 해두어도 상관없다...)

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

앞서 세워둔 문제해결전략을 코드로 그대로 옮겨적은 것이다

for x in wall:
    lab2 = copy.deepcopy(lab)
    a, b, c = x[0], x[1], x[2]
    lab2[a[0]][a[1]] = 1
    lab2[b[0]][b[1]] = 1
    lab2[c[0]][c[1]] = 1
    Q = deque()
    cnt = 0
    for i in range(N):
        for j in range(M):
            if lab[i][j] == 2:
                Q.append((i, j))
                
    while Q:
        x, y = Q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if -1< nx< N and -1< ny< M:
                if lab2[nx][ny] == 0:
                    lab2[nx][ny] = 2
                    Q.append((nx, ny))
                    
    for i in range(N):
        for j in range(M):
            if lab2[i][j] == 0:
                cnt += 1
                
    ans = max(ans, cnt)