백준 연구소 코드 및 해설 (파이썬)

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

14502번: 연구소

 

최적의 벽 세우기를 알고리즘으로 생각하긴 너무 어려운 것 같아서.. 그냥 모든 combination으로 계산해보는 걸로 코드를 짜봤다. Python3으로는 시간초과고 PyPy3로는 통과라서 약간 찜찜하지만~ 그래도~~

입력으로 주어진 연구소를 graph, 연구소에서 벽을 세울 수 있는 빈 곳의 좌표는 blank, 바이러스의 좌표는 virus에 저장했다.

compute_safe 함수로는 입력으로 주어진 연구소 상태에 따라 안전 지대의 너비를 계산했다. 우선 바이러스의 좌표를 큐에 넣고, 하나씩 pop하면서 그 바이러스의 상하좌우 중 N*M 안에 있고, 비어있는 곳(값이 0인 곳)이 있다면 그 곳에 바이러스를 감염시키고, 그 좌표를 큐에 첨가했다. 이를 큐가 빌 때까지 반복했다. 이후 연구소에 남은 빈 곳(0)의 개수를 세서 답으로 반환했다.

itertools의 combinations를 이용해 빈 곳 3개를 선택하는 모든 경우를 구하고, 각 경우에 따라 compute_safe 함수로 안전 지대를 계산했다. 이때 graph를 deepcopy하는 것이 중요하다. 안 그러면 전에 벽을 세운 곳에 그대로 벽이 남아 있어서 벽이 엄청 많아진다.. 

마지막으로 구한 안전 지대의 너비 중 최댓값을 프린트하면 끝~

 

import sys
from itertools import combinations
from collections import deque
import copy

N, M = map(int, sys.stdin.readline().split())
graph = [] # 연구소
blank = [] # 벽을 세울 수 있는 빈 곳의 좌표
virus = [] # 바이러스의 좌표
for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    for j, x in enumerate(row):
        if x == 0:
            blank.append((i,j))
        if x == 2:
            virus.append((i,j))
    graph.append(row)

# 상하좌우
UDLR = [(-1,0), (1,0), (0,1), (0,-1)]
# 주어진 연구소 상태에 따라 안전한 곳의 너비를 계산
def compute_safe(graph, virus, N, M):
    q = deque(virus)
    while q:
        cur = q.popleft()
        pos = []
        for udlr in UDLR:
            pos.append(tuple([sum(x) for x in zip(cur, udlr)]))
        for p in pos:
            a,b = p
            if a in range(0,N) and b in range(0,M) and graph[a][b] == 0:
                graph[a][b] = 2
                q.append((a,b))
    ans = 0
    for row in graph:
        ans += row.count(0)
    return ans

# 모든 빈 곳 중 3개 선택
combs = list(combinations(blank, 3))

# 안전한 너비의 최댓값
max_safe = 0
for comb in combs:
    # new_graph = [x[:] for x in graph]
    new_graph = copy.deepcopy(graph) # deepcopy
    # 현재 combination으로 벽 세우기
    for c in comb:
        a,b = c
        new_graph[a][b] = 1
    max_safe = max(max_safe, compute_safe(new_graph, virus, N, M))

print(max_safe)