14502 연구소
문제 요약
벽을 세 개 만들어 바이러스가 퍼지는 것을 막아 안전한 공간의 최대 크기를 구한다.
시행착오
idea
- 연구실의 최대 크기가 64칸밖에 되지 않는다. (₆₄C₃= 41664)
- 벽을 세울 수 있는 모든 경우의 수에 대해 안전 영역의 칸 수를 구한다.
- 그 중 최솟값을 구하면 된다.
코드
#! /usr/bin/env python3
from collections import deque
import copy
import time
VIRUS = 2
WALL = 1
FREE = 0
n, m = map(int, input().split())
labMap = [[] for _ in range(n)]
for i in range(n):
labMap[i] = list(map(int, input().split()))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def valid(graph, x, y):
return (x<n and x>-1 and y<m and y>-1 and graph[x][y]==0)
# (sx, sy)에 존재하는 바이러스가 퍼지는 경로를 그래프에 표시
def spread(graph, sx, sy):
q=deque()
q.append((sx, sy))
while q:
x, y = q.popleft()
for i in range(4):
nextX = x + dx[i]
nextY = y + dy[i]
if not valid(graph, nextX, nextY):
continue
q.append((nextX, nextY))
if graph[x][y] == VIRUS:
graph[nextX][nextY] = VIRUS
# graph에서 안전 영역의 개수를 반환.
def countSafety(graph):
result = 0
for x in range(n):
for y in range(m):
if graph[x][y] == FREE:
result += 1
return result
# graph에서 바이러스들의 위치를 반환
def findVIRUS(graph):
result = []
for x in range(n):
for y in range(m):
if graph[x][y] == VIRUS:
result.append((x, y))
return result
################# n*mC3 가지 경우의 수에 대한 시뮬레이션 #################
result = []
start = time.time()
for i in range(n*m):
lab1 = copy.deepcopy(labMap)
w1 = (int(i/m), i%m)
if lab1[w1[0]][w1[1]] != FREE:
continue
lab1[w1[0]][w1[1]] = WALL
for j in range(n*m):
lab2 = copy.deepcopy(lab1)
w2 = (int(j/m), j%m)
if lab2[w2[0]][w2[1]] != FREE:
continue
lab2[w2[0]][w2[1]] = WALL
for k in range(n*m):
lab3 = copy.deepcopy(lab2)
w3 = (int(k/m), k%m)
if lab3[w3[0]][w3[1]] != FREE:
continue
lab3[w3[0]][w3[1]] = WALL
for virus in findVIRUS(lab3):
spread(lab3, virus[0], virus[1])
result.append(countSafety(lab3))
end = time.time()
print(max(result))
print('걸린 시간: {0:.5f} sec'.format(end-start))
문제
조합을 사용하지 않고 중복을 포함한 모든 경우의 수 (64X64X64)에 대해 계산했다.
최악의 경우 64*64*64*64*64(약 10억)번의 기본 연산을 실행하게 된다.
forloop (i ~ n*m)forloop (j ~ n*m)forloop (k ~ n*m)findVIRUSO(n*m)- spread O(n*m)
해결
C/C++ 기준으로 10억번의 연산에 걸리는 시간은 대략 1초정도인데 파이썬은 기본적으로 인터프리터를 통해 실행되기 때문에 이를 따라갈 수 없다.
하지만 PyPy3을 사용하면 파이썬의 속도를 매우 높일 수 있다.
boj에서 보여주는 시간이 최악의 경우 걸린 시간이라면 10초대에서 0.003초까지 빨라졌다…
조합을 적용하여 성능 개선
순열이 아닌 조합을 적용하여 탐색하는 노드의 개수를 줄였다.
PyPy3를 사용하지 않고 시간제한내에 정답을 찾을수 있게 되었다.
from collections import deque
import time
VIRUS = 2
WALL = 1
FREE = 0
n, m = map(int, input().split())
labMap = [[] for _ in range(n)]
for i in range(n):
labMap[i] = list(map(int, input().split()))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def valid(graph, x, y):
return (x<n and x>-1 and y<m and y>-1 and graph[x][y]==0)
def spread(graph, sx, sy):
q=deque()
q.append((sx, sy))
while q:
x, y = q.popleft()
for i in range(4):
nextX = x + dx[i]
nextY = y + dy[i]
if not valid(graph, nextX, nextY):
continue
q.append((nextX, nextY))
if graph[x][y] == VIRUS:
graph[nextX][nextY] = VIRUS
def countSafety(graph):
result = 0
for x in range(n):
for y in range(m):
if graph[x][y] == FREE:
result += 1
return result
def findVIRUS(graph):
result = []
for x in range(n):
for y in range(m):
if graph[x][y] == VIRUS:
result.append((x, y))
return result
def dcopy(dest, src):
for x in range(n):
for y in range(m):
dest[x][y] = src[x][y]
wall = []
maxSafety = 0
count = 0
# dfs 방식으로 벽을 세 개 설치하는 모든 경우의 수(₆₄C₃)에 대해 안전 영역 계산
def combination(index):
global count
global wall
global maxSafety
global labMap
# 벽 세 개 설치 후 바이러스가 퍼진 뒤 안전 영역 넓이 측정
if len(wall) == 3:
count += 1
data = [[-1]*m for _ in range(n)]
dcopy(data, labMap)
for w in wall:
data[w[0]][w[1]] = WALL
for virus in findVIRUS(data):
spread(data, virus[0], virus[1])
maxSafety = max(maxSafety, countSafety(data))
return
else:
for i in range(index, n*m):
x, y = int(i/m), i%m
if labMap[x][y] == FREE:
wall.append((x, y))
combination(i+1)
wall.pop()
else:
continue # 벽을 설치할 수 없는 공간
# print('경우의 수: {0}'.format(count))
################# n*mC3 가지 경우의 수에 대한 시뮬레이션 #################
start = time.time()
combination(0)
end = time.time()
print(maxSafety)
print('걸린 시간: {0:.5f} sec'.format(end-start))
PyPy3을 사용하지 않아도 시간제한내에 문제를 해결할수 있었다.
Comments