[백준/Python] 14502 연구소

문제 링크

14502번: 연구소

 

문제 풀이

• 벽을 3개 세울 수 있으므로 먼저 그 경우를 구해야 한다. 이후 각 경우 별로 벽을 세운 이후에 바이러스가 최대한 퍼지게 한다. 바이러스가 모두 퍼졌을 때의 빈 공간의 개수를 구하고, 최대가 될 때를 구하면 된다.
• 먼저, 바이러스 위치와 현재 빈 공간을 각각 리스트(virus, wall)에 담는다.
• 빈 공간에 3개의 경우(combinations(wall, 3))를 구하고, 벽을 설치(labc[j[0]][j[1]])한다.
• 바이러스가 최대로 퍼지게 하고(spread(virus)), 이 경우에서의 빈 공간(count(0))의 개수를 구한다.

 

전체 코드

import sys
from itertools import combinations
from collections import deque
import copy
input = sys.stdin.readline

def spread(s):
    count = 0
    queue = deque()
    for v in s:
        queue.append(v)

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and labc[nx][ny] == 0:
                labc[nx][ny] = 2
                queue.append((nx, ny))
  
    for i in range(n):
        for j in range(m):
            if labc[i][j] == 0:
                count += 1
    
    return count

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

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

virus = []
wall = []
for i in range(n):
    for j in range(m):
        if lab[i][j] == 0:
            wall.append([i, j])
        if lab[i][j] == 2:
            virus.append((i, j))

res = 0
for i in combinations(wall, 3):
    labc = copy.deepcopy(lab)
    for j in i:
        labc[j[0]][j[1]] = 1
    res = max(res, spread(virus))

print(res)