문제 링크 : https://www.acmicpc.net/problem/14502
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
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
이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
처음에는 '설마 벽 세우는 모든 경우의 수를 따져보아야 하나' 생각했었다. 그렇게 무대뽀로 푼다고?? 하면서 벽을 잘 세우면서 바이러스를 촥촥 퍼트려보는 그런 방법이 있지 않을까 계속 팔짱을 끼고 생각을 해 보았는데... 생각이 잘 떠오르지 않았다. 그래서 일단 브루트 포스로 풀어보자 했다.
import sys
import copy
from collections import deque
input =sys.stdin.readline
n, m = map(int, input().split()) # 세로 n 가로 m
lab = [list(map(int, input().split())) for _ in range(n)]
answer = 0
q = deque()
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs() :
global answer
cnt = 0
arr = copy.deepcopy(lab)
for i in range(n) :
for j in range(m) :
if arr[i][j] == 2 :
q.append([i, j])
while q :
v = q.popleft()
for i in range(4) :
nx = v[0] + dx[i]
ny = v[1] + dy[i]
if 0 <= nx < n and 0 <= ny < m :
if arr[nx][ny] == 0 :
q.append([nx, ny])
arr[nx][ny] = 2
for line in arr :
cnt += line.count(0)
answer = max(answer, cnt)
def makewall(wallcount) :
if wallcount == 3 :
bfs()
return
else :
for i in range(n) :
for j in range(m) :
if lab[i][j] == 0 :
lab[i][j] = 1
makewall(wallcount + 1)
lab[i][j] = 0
makewall(0)
print(answer)
백트래킹을 이용하여 벽을 세운다. 0인 칸을 발견하면 거기에 벽을 세우고, wallcount를 1 늘리고 다시 makewall 함수를 실행한다. 그 후 다시 0으로 만들어서 초기화 해준다. 그리고 wallcount가 3이면 3개의 벽을 다 세운 것이니 이제 이렇게 벽을 세우면 바이러스가 어찌 되는지 퍼뜨려 본다. 바이러스를 퍼뜨리는 것은 bfs로 쉽게 구현할 수 있었다. 퍼뜨린 후에 0인 칸, 즉 바이러스가 퍼지지 않은 칸의 개수를 세서 최댓값을 갱신한다.
정말 무식한 풀이이지만 달리 방법이 떠오르지 않았고... 일단 제출해 보니 python3에서는 어림없이 시간 초과가 났다. 지푸라기라도 잡는 심정으로 pypy3으로 제출했더니 통과됐다.
그 다음에는 시간을 줄일 수 있는 방법이 있을까에 대해 고민했다.
그러던 중, 아무것도 없는 허허벌판에 생뚱맞게 벽 3개를 세우는 것이 의미가 없다고 판단했다. 바이러스를 막는게 목표이니까... 아무래도 벽이나 바이러스와는 서로 인접해 있어야 하지 않을까? 그냥 맨땅에 박아버리면 바이러스를 막는 역할을 하지 못할 것이다. 그건 그냥... 기둥이니까?
그런데 대각선으로 인접해 있으면 그건 벽으로써 유효하다.
0 0 1
0 1 0
1 0 2
이런 식으로 벽이 구성되어 있다면 좌측 3칸을 지킬 수 있다. 즉
상하좌우 + 대각선 총 8방향을 살펴 보았을 때 벽이나 바이러스가 없는 칸은 무의미하다.
라는 추론을 했다. 그리고 코드를 조금 수정했다.
import sys
import copy
from collections import deque
input =sys.stdin.readline
n, m = map(int, input().split()) # 세로 n 가로 m
lab = [list(map(int, input().split())) for _ in range(n)]
answer = 0
q = deque()
def bfs() :
global answer
cnt = 0
arr = copy.deepcopy(lab)
for i in range(n) :
for j in range(m) :
if arr[i][j] == 2 :
q.append([i, j])
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while q :
v = q.popleft()
for i in range(4) :
ny = v[0] + dy[i]
nx = v[1] + dx[i]
if 0 <= nx < m and 0 <= ny < n :
if arr[ny][nx] == 0 :
q.append([ny, nx])
arr[ny][nx] = 2
for line in arr :
cnt += line.count(0)
answer = max(answer, cnt)
def makewall(wallcount) :
if wallcount == 3 :
bfs()
return
else :
dx = [-1, 0, 1, 1, 1, 0, -1, -1]
dy = [-1, -1, -1, 0, 1, 1, 1, 0]
for i in range(n) :
for j in range(m) :
if lab[i][j] == 0 :
flag = 0
for a in range(8) :
ny = i + dy[a]
nx = j + dx[a]
if 0 <= ny < n and 0 <= nx < m :
if lab[ny][nx] in (1, 2) :
flag = 1
break
if flag :
lab[i][j] = 1
makewall(wallcount + 1)
lab[i][j] = 0
makewall(0)
print(answer)
bfs에서 사용했던 것처럼, nx ny를 이용해 8방향에 벽이든 바이러스든 뭐가 있는지 확인하고, 뭐가 없다면 그냥 pass 하였다.
시간이 절반 가까이 줄어들었다. 하지만 여전히 python3으로는 시간초과가 뜬다는 것...
더 멋있게 벽을 세울 수 있는 방법이 있을 텐데... 일단 지금으로선 여기까지가 나의 한계