문제 : Gold 4
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
import sys
sys.stdin = open("input.text", "rt")
from collections import deque
import copy
input = sys.stdin.readline
# 0의 개수
n,m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
#0 빈칸, 1 벽 2 바이러스
#벽 3개 세워야함.
#벽 세우고 안전영역 개수 구해야함.
dx = [1,-1,0,0]
dy = [0,0,1,-1]
res = 0
def BFS(): #벽 3개를 만들면 이제 실행하는거야
global res
dq = deque()
temp = copy.deepcopy(g) #그래프를 옮긴다.
for i in range(n):
for j in range(m):
if g[i][j] == 2: #바이러스
dq.append((i,j)) #미리 닮아둬야지 ! 먼저 있는 것들부터 퍼져야함.
while dq:
x,y = dq.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<m: #경계선
if temp[nx][ny] == 0: #빈칸인 경우 바이러스로 채워야지
temp[nx][ny] = 2 #방문처리라고 생각
dq.append((nx,ny))
#전부 다 돌면서 바이러스 퍼트렸따면 이제 안전지대 개수
cnt = 0
for i in range(n):
for j in range(m):
if temp[i][j] == 0:
cnt += 1
res = max(res,cnt)
def wall(cnt): #벽을 3개 만들어야한다 즉 조합으로 빈칸 중에 3곳 뽑음
if cnt == 3:
BFS()
return
for i in range(n):
for j in range(m):
if g[i][j] == 0: #선택
g[i][j] = 1 #중복체크를 했기 때문에 다음번에 또 뽑지 않는다!
wall(cnt+1)
g[i][j] = 0 #백트랙킹시 원상복구
wall(0)
print(res)코멘트
처음에 벽을 어떻게 세워야할지 고민했다.
분명 움직이는 것은 바이러스이기에 그래프를 탐색하면서 바이러스(2)를 큐에 넣어야 한다는 생각은 했다.
BFS + 생각해야할 것이 좀 있는 문제이다.
결국 벽 3개를 어디에 세울지 모르니.. 진짜 다 해보는 수밖에 없다.
- 모든 경우의 수에 대해 수행해야 한다 !
(3개를 꼭 심어야 하니 조합을 떠올렸어야)
벽을 3개 설치하는 모든 경우의 수를 다 계산하자.
따라서 (1,1) ~ (n,m)까지 빈칸을 순서대로 하나씩 3개 선택하여 벽을 세우고 BFS를 수행한 후 벽을 지우고(백트랙킹 후 필수!) 그 다음칸에 대해 다시 벽을 세우고 BFS를 수행하고 벽을 지우는 방식을 반복해야한다.
⚽ copy 모듈
-
이번에 처음 쓰게 되었는데, copy 모듈은 맵 정보를 깊은 복사(deep copy)하여 벽 3개를 세울 수 있는 모든 경우의 수에서 벽의 설정, 바이러스 전파를 따로 표현하여 사용하기 위해 import 해야했다. 깊은 복사는 복사된 데이터를 변경해도 원본 데이터가 변경되는 것을 방지한다 !
-
테스트할 때마다 깊은 복사 해줘야 한다.바이러스 이동할 때마다 0을 2로 만드는데 되돌릴 수가 없기 때문.
⚽ 이 문제는 BFS + 조합 문제였다. 먼저 조합으로 그래프에 벽 3개를 설치후 BFS 돌려서 안전지대 개수 구한다. 이 과정을 끝까지 반복. 그렇게 얻어낸 최대 크기 구하면 되는데... 이렇게 특정 알고리즘 + @ 인 경우 문제를 잘 해석할 수 있어야 한다.
⚽ 조합 코드에서 0을 만날 때마다 그래프 값을 1로 변경(벽), 그리고 다시 호출해서 cnt를 1 증가시킨다. 백 트랙킹시 원상복구 (0) 필수 !
- (조합 부분 다시 공부해야겠따...)
