백준 알고리즘 14502번 연구소 풀이 with Python

문제 링크: https://www.acmicpc.net/problem/14502

14502번: 연구소

문제는 다음과 같습니다.

백준 알고리즘 14502번 연구소 문제

처음에 연구소를 바이러스에 감염시켰다가 다시 복원하는 작업을 하였는데, 시간 초과가 발생하였다. 

그래서 복원하는 것을 하지 않고, python의 copy 모듈을 사용하여 깊은 복사를 이용하여 이를 해결하였다.

그리고 기둥을 3개 세우는 경우의 수를 계산하기 위해서 python itertools 모듈의 combinations를 사용하였다.

 

#문제 해결에 필요한 모듈들을 불러옵니다.
import copy
from itertools import combinations
"""문제를 해결하기위한 함수인 infect2함수입니다.
	바이러스의 처음위치 x,y가 주어졌을 때, 계속 퍼져나가는 함수입니다."""
def infect2(x,y,map1):
    n=len(map1)
    m=len(map1[0])
    dx=[-1,0,1,0]
    dy=[0,-1,0,1]
    for i in range(4):
        if -1<x+dx[i]<n and -1<y+dy[i]<m:
            if map1[x+dx[i]][y+dy[i]]==0:
                map1[x+dx[i]][y+dy[i]]=2
                infect2(x+dx[i],y+dy[i],map1)
            else:
                continue
        else:
            continue
#문제 해결을 위한 핵심 함수입니다. 바이러스 개수만큼 바이러스를 퍼트립니다.
def infect(virus,map1,c):
    n=len(virus)
    global answer
    #바이러스 개수만큼 퍼트렸다면, 안전구역의 구역을 카운트하여 answer값과 비교합니다.
    if c==n:
        sub=counter(map1)
        if answer<sub:
            answer=sub
            return
        
    else:
        x,y=virus[c]
        infect2(x,y,map1)
        infect(virus,map1,c+1)
#안전구역을 카운트하기위한 함수입니다.
def counter(map1):
    n=len(map1)
    m=len(map1[0])
    count=0
    for i in range(n):
        for j in range(m):
            if map1[i][j]==0:
                count+=1
    return count
# n,m을 입력받습니다.
n,m=map(int,input().split())
#answer의 초기값을 -1로 초기화합니다.
answer=-1
lab=[]
virus=[]
zeros=[]
#lab변수에 연구소 필드값을 받습니다.
for _ in range(n):
    lab.append(list(map(int,input().split())))
# virus와 zeros에 각각 바이러스 위치와 0의 위치들을 넣습니다. 
for i in range(n):
    for j in range(m):
        if lab[i][j]==2:
            virus.append([i,j])
        elif lab[i][j]==0:
            zeros.append([i,j])
# 0값인 것들중에 3개씩 묶인 조합을 통해서 기둥을 세우고, 바이러스를 퍼트립니다.
zeros=list(combinations(zeros,3))
for i in zeros:
    lab2=copy.deepcopy(lab)
    for j in range(3):
        lab2[i[j][0]][i[j][1]]=1
    infect(virus,lab2,0)
    for j in range(3):
        lab2[i[j][0]][i[j][1]]=0
print(answer)