[14502] 연구소

Young Min Kang·2024년 1월 29일

Baek Joon

목록 보기

30/39

코딩 테스트 양식

😲 문제

출처
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
입력
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
출력
27

❗️ 문제 재정의

문제의 조건 다음과 같다.
1. 바이러스는 상하좌우로 퍼진다.
2. 바이러스는 벽을 뚫지 못한다.
3. 벽을 추가로 세 개를 세워 최대 안전구역을 확보하라.

최대 안전구역을 구해야하는데 그렇다면 조건을 참고하여 다시 절차적으로 바꿔보자.
1. 벽을 세 개를 세운다.(중복되지 않는 조합을 구하여라.)
2. 바이러스를 퍼뜨린다.(BFS를 통해 바이러스를 퍼뜨려라.)
3. 안전영역의 수를 카운트한다.(0의 개수를 카운트한다.)

✔ 계획 수립

행의 개수 n과 열의 개수 m을 받는다.
바이러스가 아직 퍼뜨려지지 않았고 추가 벽 3개를 세우기 전의 지도 상태를 받는다.
0의 위치를 구하고 해당 0의 위치에서 3개를 중복되지 않게 뽑는다.(combination)
뽑은 3개의 위치에 벽을 세운다. (0->1로 변경)
벽을 세운 새로운 지도에서 바이러스를 bfs로 퍼뜨린다.
남은 0의 수를 구한다.
최대 값인지 비교한다.
3~6번 반복

👨🏻‍💻 문제 풀이

from itertools import combinations
from collections import deque
from copy import deepcopy
import sys
input = sys.stdin.readline
# 0은 빈 칸, 1은 벽 2는 바이러스
# 연구소의 지도가 주어졌을 경우 
# 벽을 세 개 세운 후 가장 큰 안전영역을 구하여라

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

# 특정 0을 세 개를 중복되지 않게 뽑아야 한다. 몇 가지 경우의 수가 나오며,
zero_area = []
virus = deque()
for i in range(n):
    for j in range(m):
        if map[i][j] == 0:
            zero_area.append((i,j))
        if map[i][j] == 2: 
            virus.append((i,j))
make_wall = list(combinations(zero_area,3))

# 바이러스를 퍼뜨려야한다.
max_safety = 0

for walls in make_wall: 
    # 벽을 뽑고 벽을 세워야함.
    temp_map = deepcopy(map)
    for wall in walls:
        temp_map[wall[0]][wall[1]] = 1 # 추가 벽 세우기
    # 새로 벽을 세웠으니 바이러스를 퍼뜨려야함. bfs
    moves = [(0,1),(1,0),(-1,0),(0,-1)]
    temp_virus = deepcopy(virus)
    while temp_virus:
        x,y = temp_virus.popleft()
        for dx, dy in moves:
            nx, ny = x+dx, y+dy
            if 0<=nx<n and 0<=ny<m and temp_map[nx][ny]==0:
                temp_map[nx][ny] = 2
                temp_virus.append((nx,ny))
    cnt = 0
    # 청정지역을 찾아야함.
    for i in range(n):
        for j in range(m):
            if temp_map[i][j] == 0:
                cnt +=1
    # 최대 안전구역 크기를 구해야함.
    max_safety = max(max_safety, cnt)
print(max_safety)