연구소 3
접근 방법 [필수 작성]
제한 조건 확인
연구소 크기 최대 50x50
활성 가능 바이러스 갯수 최대 10개
비활성 바이러스가 활성바이러스랑 만나면 활성바이러스가 됨 → 근데 어차피 그냥 지나갈수있는 길이었기 때문에 딱히 고려 안해도 됨 → 잘못된 생각임
비활성 바이러스도 바이러스 칸이어서 만약 비활성바이러스만 남기고 다 바이러스 전염됐으면 최소시간이 달라질 가능성이 있음
→ 비활성 바이러스가 활성바이러스가 됐을때는 비활성바이러스 칸을 시간으로 바꿔주면 안된다. 원래 바이러스칸이었기 때문에. 그래서 ‘*’ 다음칸부터 +1된 값을 넣어주면 된다.
ex) 7초 전염 바이러가 비활성바이러스에 도착
→ 비활성바이러스칸이 8초가 되어야하지만, 8초로 바꿔주지 않고 그냥 ‘*’ 로 놔둔다.
→ 활성바이러스가 된 ‘*’ 칸은 다음칸부터 9초 로 바이러스를 전파한다.
- 구해야할 값
연구소 모든 가능한 칸을 바이러스로 퍼뜨릴 수 있는 최소시간
모든 가능한 칸에 바이러스 퍼뜨릴 수 없으면 -1 리턴
아이디어
선택할 수 있는 활성바이러스 조합을 고른다.
바이러스 활성 시켜서 전파시킨다. 이때 전파될때마다 현재 시간을 해당칸에 기록한다.
다 전파된 후 다시 모든 노드를 탐색하면서 시간기록 중 최대값을 찾는다. 이때, 벽이 아닌 감염되지 않은 노드가 발견되면, -1 를 리턴하고 종료한다.
만약 matrix 탐색 함수가 -1이 아니고, 현재 확산시간 보다 더 작은 확산시간이면 확산시간을 업데이트한다.
비활성 바이러스 처리도
시간복잡도
활성바이러스 선택 최대 조합 수 = 10C5 = 252
각 조합의 바이러스 전파에 걸리는 최대 연산수 = 55050 (대충) = 12500
0이 있는지 판단 = 50*50 = 2500
전체 = 252 * 15000
자료구조
필요한 함수
def 활성 바이러스 전파 함수(활성바이러스 인덱스)
def 확산시간계산 함수(감염매트릭스)
→ -1 인 값 찾으면 -1 리턴
→ -1 인 값이 하나도 없으면 ‘*’ 와 ‘-’ 가 아닌 값들 중에 가장 큰 수를 리턴
코드 구현 [필수 작성]
1차 시도 (소요시간 1시간20분)
한방에 통과!
from collections import deque
from itertools import combinations
import copy
import sys
N, M = map(int,input().split())
matrix = []
for _ in range(N):
matrix.append(list(map(int,input().split())))
dr = [0,1,0,-1]
dc = [1,0,-1,0]
inactive_virus_index_list = []
visited = [[False]*N for _ in range(N)]
min_infection_time = sys.maxsize
def print_matrix(matrix):
for i in range(len(matrix)):
print(matrix[i])
def change_to_default_matrix(input_matrix): #감염시작 직전 매트릭스로 바꿔주는 함수
for r in range(len(input_matrix)):
for c in range(len(input_matrix[0])):
if input_matrix[r][c] == 1:
input_matrix[r][c] = '-'
elif input_matrix[r][c] == 2:
input_matrix[r][c] = '*'
else:
input_matrix[r][c] = -1
return input_matrix
def max_infection_time(input_matrix):
tmp_time = -1
for r in range(len(input_matrix)):
for c in range(len(input_matrix[0])):
if input_matrix[r][c] == -1:
return -1
elif type(input_matrix[r][c]) == int and input_matrix[r][c] > tmp_time:
tmp_time = input_matrix[r][c]
return tmp_time
for r in range(N):
for c in range(N):
if matrix[r][c] == 2:
inactive_virus_index_list.append((r,c))
for active_virus_index_list in combinations(inactive_virus_index_list,M):
q = deque([])
tmp_visited = copy.deepcopy(visited)
infected_matrix = change_to_default_matrix(copy.deepcopy(matrix))
for active_virus_index in list(active_virus_index_list):
q.append([active_virus_index,0]) # [(r,c),0]
tmp_visited[active_virus_index[0]][active_virus_index[1]] = True
infected_matrix[active_virus_index[0]][active_virus_index[1]] = 0
while q:
index, infection_time = q.popleft()
tr = index[0]
tc = index[1]
for i in range(4):
nr = tr + dr[i]
nc = tc + dc[i]
if 0 <= nr < N and 0 <= nc < N and tmp_visited[nr][nc] == False:
if infected_matrix[nr][nc] == -1:
q.append([(nr,nc),infection_time + 1])
tmp_visited[nr][nc] = True
infected_matrix[nr][nc] = infection_time + 1
elif infected_matrix[nr][nc] == '*':
q.append([(nr,nc),infection_time + 1])
tmp_visited[nr][nc] = True
max_infect_time = max_infection_time(infected_matrix)
if max_infect_time != -1:
min_infection_time = min(min_infection_time,max_infect_time)
if min_infection_time == sys.maxsize:
min_infection_time = -1
print(min_infection_time)
배우게 된 점 [ 필수 X ]
자유 형식
질문 [ 필수 X ]
자유 형식
피드백 [ 코치 작성 ]
수고하셨습니다!
