[Python][백준]17142번 연구소3

https://www.acmicpc.net/problem/17142

공부 날짜 : 2022.09.24
정답 참조 여부 : X

연구소 내에 특정위치에 바이러스가 있을 때, 바이러스가 확산되어 모든 빈칸을 채울 수 있는지, 있다면 최소 시간은 얼마인지 구하는 문제이다.

---

문제가 쉬웠다면 쉬웠고 어려웠다면 어려웠다.
문제만 읽고 푼 첫 코드가 바로 80퍼까지 채점이 되었고 계속 틀렸다고 나왔다. 틀린이유는 문제를 제대로 안읽은 "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다."의 내용 때문

초기 코드에서는 0인 경우에만 확산하고 2인경우는 무시되어서

9 1
0 2 2 2 2 2 2 2 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1

의 테스트 케이스가 1로 답이 나오는 문제가 있었다.(답은 4)

해당 부분을 수정하기위해 활성바이러스를 3으로 두고 비활성바이러스를 만났을때 확산이 아닌 활성화만 시켜주는 식으로 코드를 수정했고 기존 코드는 유지하고 조건을 바꾸다 보니 조금 어려웠다.

무엇보다 언어에 따른 시간제한 차이로 시간초과 나와도 PyPy3로 하면 된다는 보험이 없어져서 최대한 시간단축을 위해 신경을 썼다.

소스코드

import sys
from copy import deepcopy
input = sys.stdin.readline

lab = []
virus_postion = []
n,m = map(int, input().split())

#바이러스가 모두 확산되었는지 판단하기 위한 빈칸의 개수
count_null = 0

for i in range(n):
    a = list(map(int,input().split()))
    for j in range(n):
        if a[j] == 2:
            #바이러스의 위치와 확산에 걸린 시간을 저장
            virus_postion.append([i,j,0])
        elif a[j] == 0:
            count_null += 1
    lab.append(a[:])

#최종 출력하게될 시간    
min_time = int(10e9)

#바이러스 중에서 활성화 시킬 바이러스를 고르는 dfs
def select_virus(depth,select,start):
    #활성화 시킬 바이러스를 다 골랐으면 확인
    if depth == m:
        deffusion(deepcopy(select))
        return
    
    for i in range(start,len(virus_postion)):
        select.append(virus_postion[i])
        select_virus(depth+1,select,i+1)
        select.remove(virus_postion[i])

        
dx = [0,1,0,-1]
dy = [1,0,-1,0]


#활성화된 바이러스를 확산시키는 함수
def deffusion(select):
    global min_time
    
    max_time = 0
    virus_count = 0
    temp_lab = deepcopy(lab)
    
    
    #bfs를 위한 반복
    while select:
        x,y,time = select.pop(0)
        #활성된 바이러스는 3으로 표시
        temp_lab[x][y] = 3
        
        #빈칸이 모두 채워진 경우에
        if virus_count == count_null:
            min_time = min(min_time, max_time)
            return
        
        #연산시간 단축을 위해 현재 시간이 최소 시간 이상이면 리턴
        if time >= min_time:
            return
        
        #모든 방향에 대하여
        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]
            
            #범위 이내인경우에
            if 0 <= nx < n and 0 <= ny < n:
                #빈칸이면 확산, 확산된 수를 체크
                if temp_lab[nx][ny] == 0:
                    virus_count += 1
                    temp_lab[nx][ny] = 3
                    select.append([nx,ny,time+1])
                    max_time = time + 1
                #비활성 바이러스를 만나면 활성 바이러스로
                elif temp_lab[nx][ny] == 2:
                    temp_lab[nx][ny] = 3
                    select.append([nx,ny,time+1])
        
     

        
        
select_virus(0,[],0)

if min_time == int(10e9):
    print(-1)
else:
    print(min_time)