[코테준비] 9. 백준- 연구소3 (17142) python "삼성 SW 역량 테스트 기출 문제"

연구소3

• 링크:https://www.acmicpc.net/problem/17142
• 난이도:골드 3
• 분류: 그래프이론, 브루트포스 알고리즘, 그래프 탐색, BFS
• 직접 푼 여부: X

풀이 노트

• "연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. " 
  • 모든 칸에 바이러스가 있으면 된다. 굳이 다 활성 바이러스일 필요는 없다.

 

• 아래 velog에서 잘 정리해주셔서 참고하여 문제를 풀었습니다.
• 풀이 순서는
  • 1. 활성화할 바이러스를 m개 고른다. itertools를 쓰지 않고 dfs사용. (select_virus)
  • 2. 다 고르면, 해당 바이러스들을 확산 시킨다. bfs사용 (defussion)
• 간단한 변수명을 제 취향에 맞게 바꾸고, 이해를 하며 주석을 추가하였습니다. 그리고 바이러스를 고르는 def에서 list를 def에서 넘겨받지 않고, global로 설정해서 푼 풀이가 아래 정답코드 입니다. 원본 풀이가 궁금하신분은 아래 링크를 확인해주시기 바랍니다!
• 참고: https://velog.io/@7h13200/Python%EB%B0%B1%EC%A4%8017142%EB%B2%88-%EC%97%B0%EA%B5%AC%EC%86%8C3

 

정답 코드 💻

# 연구소 3
# 참고: https://velog.io/@7h13200/Python%EB%B0%B1%EC%A4%8017142%EB%B2%88-%EC%97%B0%EA%B5%AC%EC%86%8C3

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

lab =[] # map
virus =[] # [좌표r,c, 확산에 걸린 시간]
n,m = map(int, input().split()) # n: 크기, m: 바이러스 개수

# 빈칸의 개수 (바이러스가 모두 확산되었는지 판단하기 위해서)
countnull =0 

for i in range(n):
    a =list(map(int, input().split()))
    for j in range(n):
        if a[j] ==2:
            virus.append([i,j,0])
        elif a[j] ==0:
            countnull +=1
    lab.append(a)

mintime = int(10e9)

# dfs : 바이러스중 활성화 시킬 바이러스를 고르는 dfs
# 코테가 아니라면, itertools combinations이 더 편하겠지만, 코테는 이를 사용못하니까! dfs로!
def choosevirus(depth, start):
    # 활성화 시킬 바이러스를 다 골랐으면 확인
    global select
    if depth ==m:
        vdeffusion(deepcopy(select))  # 바이러스 확산시키기 
        return
    
    for i in range(start, len(virus)):
        select.append(virus[i])
        choosevirus(depth+1, i+1)
        select.remove(virus[i])
        
        
dc = [-1,0,1,0]
dr= [0,-1,0,1]

# 바이러스 확산!
def vdeffusion(select):      
    global mintime
    
    temptime =0
    virus_count =0
    temp_lab = deepcopy(lab)
    
    # bfs - 확산
    while select:
        r,c,time = select.pop(0)
        temp_lab[r][c] =3  #활성으로 변경
        
        if virus_count == countnull:
            # 빈칸이 다 채워짐 (확산 다 됨)
            mintime = min(mintime, temptime)
            return
        
        if time >= mintime:
            # 지금 걸린시간이 min시간보다 길어지면, 어차피 답아니니까 return
            #temptime: 이번에 걸린 최대시간 - 이게 최대시간이 될 수 있는 이유는 select를 append할 때
            # 즉, choosevirus와 defussion에서 time이 높아지는 순으로 append를 하였기 때문에 마지막이 가장 높은 것임

            return 
        
        # 좌상우하 확산
        for dir in range(4):
            nr = r + dr[dir]
            nc = c + dc[dir]
            
            if (0<=nr<n) and (0<=nc<n):
                # 변화가 일어나는 곳 1)빈칸, 2)비활성 바이러스 있는 곳
                if temp_lab[nr][nc] ==0:
                # 1) 빈칸이면, 바이러스 개수하나 더 늘었음 (원래 빈칸이였던 것이 다 바이러스가 되면 끝이니까)
                    virus_count +=1
                    temp_lab[nr][nc] =3 # 활성바이러스
                    select.append([nr, nc, time+1]) # 활성바이러스 생겼으니까 이것도 확산 됨
                    temptime = time +1 
                elif temp_lab[nr][nc] ==2:
                    temp_lab[nr][nc] =3
                    select.append([nr, nc, time+1])#활성바이러스가 되었으니까 이것도 확산 됨
                                        
                    

 
# main 문
select =[]
select_virus(0,0)
       
        
# 정답출력       
if mintime ==int(10e9):
    #변함이 없다면 (확산 다 안됨)
    print(-1)
else:
    print(mintime)