알고리즘
백준 - 14502 연구소
이온시옥
2019. 2. 15. 22:22
반응형
# https://www.acmicpc.net/problem/14502
import copy
n = m = 0 # 지도 리스트의 NxM 크기
virus_list = [] # 바이러스(2) 위치 좌표들
arr = [] # 원본 지도 리스트
max_val = 0 # 안전영역 결과값
dx = [-1, 1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1] #
def get_safe_area(copyed):
safe = 0
for i in range(n):
for j in range(m):
if copyed[i][j] == 0:
safe += 1
return safe
def spread_virus(x, y, copyed):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if copyed[nx][ny] == 0:
copyed[nx][ny] = 2
spread_virus(nx, ny, copyed)
def set_three_walls(start, depth):
global max_val
if depth == 3:
copyed = copy.deepcopy(arr)
length = len(virus_list)
for i in range(length):
[virus_x, virus_y] = virus_list[i]
spread_virus(virus_x, virus_y, copyed)
max_val = max(max_val, get_safe_area(copyed))
return
for i in range(start, n * m):
x = int(i / m)
y = int(i % m)
if arr[x][y] == 0:
arr[x][y] = 1
set_three_walls(i + 1, depth + 1)
arr[x][y] = 0
if __name__ == '__main__':
# 사용자로부터 가로세로입력받기
n, m = input().split(' ') # n은 세로, m은 가로
n, m = int(n), int(m)
# n,m 크기조건을 만족하면, 사용자로부터 입력받음.
if 3 <= n and m <= 8:
for i in range(n):
arr.append([int(x) for x in input().split()]) # 사용자로부터 NxM에 해당하는 리스트 받기.
# print(arr)
for i in range(n):
for j in range(m):
if arr[i][j] == 2:
virus_list.append([i, j]) # 바이러스가 어디있는지 좌표 저장.
set_three_walls(0, 0) # 벽 3개 치기...
print(max_val) # 결과값 출력
else:
exit()
반응형