문제 링크

17142 - 연구소 3

문제 설명

N*N 크기의 연구소 각 칸에 빈칸, 벽 또는 바이러스가 위치한다. 바이러스는 활성과 비활성 두가지 상태로 나뉘는데 활성 상태 바이러스는 1초간 상하좌우 인접칸으로 동시에 복제되고, 초기 바이러스는 전부 비활성 상태다.
활성 바이러스가 비활성 바이러스 칸으로 가면 비활성 바이러스는 활성바이러스가 된다.
바이러스 M개를 활성 상태로 바꿨을때 모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구하라.

문제 풀이

진차 눈물 줄줄흘렸네 ㅋ,,

lab[i][j] : 연구실 (i,j)칸이 0-빈칸, 1-벽, 2-비활성 바이러스, 3-활성 바이러스 인지?
virus = []: 초기 비활성 바이러스의 좌표

pos = list(combinations(virus, M))
for p in pos:
    # 가능한 M개 뽑기 조합마다 
    for x,y in p:
        # virus 활성 상태로
        lab[x][y] = 3
    clab = copy.deepcopy(lab)
    answer = min(answer, diffusion(clab, p))
    for x,y in p:
        # virus 비활성 상태로
        lab[x][y] = 2

입력을 받고, combinations를 이용해서 가능한 M개의 바이러스 선택 경우를 구한다. 각 경우에 대해서 diffusion()함수를 이용해, 모든 빈칸을 활성 바이러스로 만드는데 걸리는 시간을 구한다.

diffusion()은 다음과 같이 구현했다.

def diffusion(board, virus):
    cur_virus = deque(virus)
    time = 0
    cur_empty = empty
    
    while cur_virus:
        if time > answer:
            return float('inf')
        # 이번 turn으로 빈칸이 없어지면
        if cur_empty == 0:
            return time
		
        # 지금 확산된 바이러스는 빼고 계산하려고
        length = len(cur_virus)
        for l in range(length):
            x, y = cur_virus.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny):
                    if board[nx][ny] == 0:
                        # 빈칸이면
                        cur_empty -= 1
                        board[nx][ny] = 3
                        cur_virus.append((nx, ny))
                    elif board[nx][ny] == 2:
                        # 비활성 바이러스면
                        board[nx][ny] = 3
                        cur_virus.append((nx, ny))
        time += 1
    # 다 돌고 빈칸이 없으면
    if cur_empty == 0:
        return time
    else:
        return float('inf')

처음에는 계속 시간초과가 나서 deepcopy의 문제인가,,, 싶어서 deepcopy대신 dictionary로 각 칸마다의 상태도 저장해보고 했다. 근데 deepcopy 문제가 아니라 첨에 설계를 잘못해서였음,, 활성 상태의 바이러스 4칸을 검사 후 append할때 검사한 바이러스도 cur_virus에 append해서 불필요한 루프를 많이 돌았다. 왜그랬니,,

전체 코드

암튼 전체 코드는 다음과 같습니다.

import sys
from itertools import combinations
from collections import deque
import copy

input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

N, M = map(int, input().split())
lab = []
virus = []
empty = 0
answer = float('inf')
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] == 0:
            # 빈칸이면
            empty += 1
        elif tmp[j] == 2:
            virus.append((i,j))
    lab.append(tmp)

def in_range(x, y):
    if x in range(N) and y in range(N):
        return True
    else:
        return False

def diffusion(board, virus):
    cur_virus = deque(virus)
    time = 0
    cur_empty = empty
    
    while cur_virus:
        if time > answer:
            return float('inf')
        if cur_empty == 0:
            return time

        length = len(cur_virus)
        for l in range(length):
            x, y = cur_virus.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny):
                    if board[nx][ny] == 0:
                        # 빈칸이면
                        cur_empty -= 1
                        board[nx][ny] = 3
                        cur_virus.append((nx, ny))
                    elif board[nx][ny] == 2:
                        # 비활성 바이러스면
                        board[nx][ny] = 3
                        cur_virus.append((nx, ny))
        time += 1
    if cur_empty == 0:
        return time
    else:
        return float('inf')

pos = list(combinations(virus, M))
for p in pos:
    # 가능한 M개 뽑기 조합마다 
    for x,y in p:
        # virus 활성 상태로
        lab[x][y] = 3
    clab = copy.deepcopy(lab)
    answer = min(answer, diffusion(clab, p))
    for x,y in p:
        # virus 비활성 상태로
        lab[x][y] = 2
if answer < float('inf'):
    print(answer)
else:
    print(-1)