문제 링크
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
문제 풀이
- 벽을 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)
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Pyhon] 14002 가장 긴 증가하는 부분 수열 4 (0) | 2024.04.04 |
---|---|
[백준/Python] 14891 톱니바퀴 (0) | 2024.04.03 |
[백준/Python] 19539 사과나무 (0) | 2024.03.22 |
[백준/Python] 2294 동전 2 (0) | 2024.03.20 |
[백준/Python] 15686 치킨 배달 (0) | 2024.03.20 |