17142 - 연구소3*

이번 문제는 시간초과만 주구장창 나오다가 결국 다른 여러 사람들의 풀이를 참고해본 문제이다...

# 가장 처음 바이러스는 비활성
# 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시 복제 : 1초
# 바이러스 M개를 활성 상태로 변경
# 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간
from copy import deepcopy
N, M = map(int, input().split())
graph = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    graph.append(tmp)

minTime = 1000000000
timeList = []
visited = [[False for _ in range(N)] for _ in range(N)]

# 바이러스를 놓는 경우의 수를 모두 정한다
def NumberOfCases(num):
    global minTime, numOfVirus
    if M == num:
        copyVisited = deepcopy(visited)
        timeOfSpreadVirus = TimeOfSpreadVirus(Transform(), copyVisited)

        timeList.append(timeOfSpreadVirus)
        if timeOfSpreadVirus >= 0:
            minTime = min(timeOfSpreadVirus, minTime)
        return

    for r in range(N):
        for c in range(N):
            if graph[r][c] == 2 and visited[r][c] == False:
                visited[r][c] = True
                NumberOfCases(num+1)
                visited[r][c] = False

# 벽 : -, 비활성 바이러스 : * , 활성 바이러스 : 0, 빈 칸 : 바이러스가 퍼지는 시간
def Transform():
    transGraph = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 2 and visited[i][j] == False:
                transGraph[i][j] = '*'
            elif graph[i][j] == 1:
                transGraph[i][j] = '-'
            else:
                transGraph[i][j] == 0
    return transGraph

dx = [1, 0, -1, 0]; dy = [0, -1, 0, 1]
def TimeOfSpreadVirus(transGraph, visited):
    time = 0; curNum = -1
    while True:
        curNum+=1
        chk1 = False; chk2 = False
        for i in range(N):
            for j in range(N):
                if (visited[i][j] == True) and (transGraph[i][j] == curNum):
                    chk1 = True
                    for d in range(4):
                        ni = i+dx[d]; nj = j+dy[d]
                        if 0<=ni<N and 0<=nj<N and transGraph[ni][nj] == 0 and visited[ni][nj] == False:
                                chk2 = True
                                transGraph[ni][nj] = curNum+1
                                visited[ni][nj] = True
                                time = max(time, transGraph[ni][nj])
        if chk2 == False:
            break

    if chk1 == False:
        return -1
    return time

NumberOfCases(0)
if minTime == 1000000000:
    print(-1)
else:
    print(minTime)

나의 경우, DFS로 활성화된 M개의 바이러스를 선택하고, While문을 통해 바이러스가 확산되는 시간을 구했다.

DFS와 While문의 조합이라 시간초과는 당연한듯해 보인다.... ㅠ.ㅠ

 

그래서 활성화할 M개의 바이러스를 구하는 것은 itertools의 combinations 메소드인 조합을 이용하고, 확산되는 시간은 BFS를 이용해 문제를 풀었다.

# 가장 처음 바이러스는 비활성
# 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시 복제 : 1초
# 바이러스 M개를 활성 상태로 변경
# 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간
import sys
from copy import deepcopy
from itertools import combinations
from collections import deque
N, M = map(int, input().split())
graph = [];  candi = []
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] == 2:
            candi.append([i, j, 0])
    graph.append(tmp)

def checkGraph(graph):
    for i in range(N):
        if 0 in graph[i]:
            return False
    return True

dx = [1, 0, -1, 0]; dy = [0, -1, 0, 1]
def bfs(virusQ, graph):
    visited = [[False for _ in range(N)] for _ in range(N)]
    graph = deepcopy(graph)
    dq = deque(virusQ)
    time = 0
    while dq:
        x, y, t = dq.popleft()
        visited[x][y] = True
        for d in range(4):
            nx = x+dx[d]; ny = y+dy[d]
            if 0<=nx<N and 0<=ny<N and graph[nx][ny] != 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                if graph[nx][ny] == 0:
                    graph[nx][ny] = 2
                    time=t+1
                dq.append((nx, ny, t+1))

    val = checkGraph(graph)
    if val:
        return time
    else:
        return -1

minTime = sys.maxsize
# 바이러스를 활성화하는 경우의 수를 모두 정한다
candidates = list(combinations(candi, M))
for virusQ in candidates:
    time = bfs(virusQ, graph)
    if minTime>time and time!=-1:
        minTime = time

if minTime != sys.maxsize:
    print(minTime)
else:
    print(-1)