[Gold III]
https://www.acmicpc.net/problem/17142
17142번: 연구소 3
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고
www.acmicpc.net
이 문제는... 사실 토마토나, 백조의 호수 같은 문제와 유사한 문제였으나, 시간이 조금 걸렸다.
문제를 푸는 핵심은, '비활성화된 바이러스 또한 전염이 진행될 수 있도록 처리할 것.'
그리고, '비활성화된 바이러스가 활성화되는 것은 최소 시간을 측정하는 데에 고려하지 않아야 할 것.'
이것들을 유념하며 문제를 풀어 나가야 한다.
풀이 1
일단 BFS 문제라는 것은 보자마자 알 수 있었다.
다만, 시간제한이 좀 빠듯할 것 같다는 생각이 들었는데...
바이러스를 놓을 수 있는 칸은 총 (M~10)개가 있고, 놓을 수 있는 바이러스의 개수가 M(1~10)개.
이 경우들을 모두 Brute-Force로 따져서 하나하나 BFS를 돌려가며 계산해보는 방법밖엔 없어서였는데,
막상 최대 갯수를 계산해 보면 10C5이므로 252개. 그리 많지는 않은 개수라 일단 안심하고 들어갔다.
모두 진행되었는지 등의 과정을 반복문 안에 막 집어넣어서 그런지 TLE 날 것이라 예상하긴 했음.
TLE.
from collections import deque
from itertools import combinations
import copy
# input
N, M = map(int, input().split())
lab = []
for _ in range(N):
lab.append(list(map(int, input().split())))
# delta row, delta col.
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]
# find 2 in laboratory.
twos = []
for r, row in enumerate(lab):
for c, i in enumerate(row):
if i == 2:
twos.append([r, c])
# Combination - (len of twos) C (M) - find all combination of index.
start = list(combinations(twos, M))
# save Minimum Second to infect all blocks.
minSec = 10000
def isAllInfected(inLab):
# function to know all blocks infected.
for row in inLab:
for c in row:
if c == 0:
return False
return True
# check if minSec = 0
if isAllInfected(lab):
print(0)
exit()
# cycle of combinations
for s in start:
sec = 0
q = deque(s)
templab = copy.deepcopy(lab)
# change numbers (wall, virus)
for i in range(N):
for j in range(N):
if templab[i][j] == 2:
templab[i][j] = -1
elif templab[i][j] == 1:
templab[i][j] = -1
# BFS - one cycle (1 case)
while q:
sec += 1
tempq = deque()
# BFS - one cycle (1 sec)
while q:
r, c = q.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
# check if wall / if virus already infected.
if N > nr >= 0 and N > nc >= 0 and templab[nr][nc] == 0:
tempq.append([nr, nc])
# save second for infect this block.
templab[nr][nc] = sec
q = copy.deepcopy(tempq)
if isAllInfected(templab):
result = max(map(max, templab))
if minSec > result:
minSec = result
if minSec != 10000:
print(minSec)
else:
print(-1)
풀이 2
1, 2와 같은 숫자를 바꾸는 과정(O(N^2))을 반복문 안에 집어넣을 필요가 없어 제거하고,
copy.deepcopy()의 사용을 줄이고,
처음부터 빈칸이 없다면 예외처리 하는 등 여러 부분을 개선.
그러나 WA.
from collections import deque
from itertools import combinations
import copy
# input
N, M = map(int, input().split())
lab = []
for _ in range(N):
lab.append(list(map(int, input().split())))
# delta row, delta col.
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]
# find 2 in laboratory / count 0 in lab / change numbers(wall, virus)
twos = []
cnt_0 = 0
for r, row in enumerate(lab):
for c, i in enumerate(row):
if i == 2:
twos.append([r, c])
lab[r][c] = "*"
elif i == 1:
lab[r][c] = "-"
elif i == 0:
cnt_0 += 1
# Combination - (len of twos) C (M) - find all combination of index.
start = list(combinations(twos, M))
# save Minimum Second to infect all blocks.
minSec = 1000000
def isAllInfected(inLab):
# function to know all blocks infected.
for row in inLab:
for c in row:
if c == 0:
return False
return True
# check if minSec = 0
if isAllInfected(lab):
print(0)
exit()
# cycle of combinations
for s in start:
sec = 0
cnt_change = 0
q = deque(s)
templab = copy.deepcopy(lab)
# BFS - one cycle (1 case)
while q:
sec += 1
tempq = deque()
# BFS - one cycle (1 sec)
while q:
r, c = q.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
# check if wall / if virus already infected.
if N > nr >= 0 and N > nc >= 0 and templab[nr][nc] == 0:
tempq.append([nr, nc])
# save second for infect this block.
templab[nr][nc] = sec
cnt_change += 1
q = tempq
if cnt_change == cnt_0:
result = sec - 1
if minSec > result:
minSec = result
# print("-------")
# for k in templab:
# print(*k)
if minSec != 10000:
print(minSec)
else:
print(-1)
풀이 3
풀이 2에서는, 비활성화된 바이러스가 활성화되지 못하도록 코드가 짜여짐.
그래서 이를 개선했음. 그러나, 비활성화된 바이러스가 활성화되는 것은 최소 시간을 측정하는 데에 영향이 가지 않아야 하나, (빈칸만 다 채워지면 ok.) 그것을 고려하지 못함.
93%에서 WA.
from collections import deque
from itertools import combinations
import copy
# input
N, M = map(int, input().split())
lab = []
for _ in range(N):
lab.append(list(map(int, input().split())))
# delta row, delta col.
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]
# find 2 in laboratory / count 0 in lab / change numbers(wall, virus)
twos = []
cnt_0 = 0
for r, row in enumerate(lab):
for c, i in enumerate(row):
if i == 2:
twos.append([r, c])
lab[r][c] = "*"
elif i == 1:
lab[r][c] = "-"
elif i == 0:
cnt_0 += 1
# Combination - (len of twos) C (M) - find all combination of index.
start = list(combinations(twos, M))
# save Minimum Second to infect all blocks.
minSec = 1000000
def isAllInfected(inLab):
# function to know all blocks infected.
for row in inLab:
for c in row:
if c == 0:
return False
return True
# check if minSec = 0
if isAllInfected(lab):
print(0)
exit()
# cycle of combinations
for s in start:
sec = 0
cnt_change = 0
q = deque(s)
templab = copy.deepcopy(lab)
# BFS - one cycle (1 case)
while q:
sec += 1
tempq = deque()
# BFS - one cycle (1 sec)
while q:
r, c = q.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
# check if wall / if virus already infected.
if N > nr >= 0 and N > nc >= 0 and (templab[nr][nc] == 0 or templab[nr][nc] == "*"):
flag = False
# if virus activated, 주변에 다른 바이러스나 빈칸 확인.
if templab[nr][nc] == "*":
for k in range(4):
kr = nr + dr[i]
kc = nc + dc[i]
if N > kr >= 0 and N > kc >= 0 and (templab[kr][kc] == "*" or templab[kr][kc] == 0):
flag = True
else:
flag = True
if flag:
tempq.append([nr, nc])
if templab[nr][nc] == 0:
cnt_change += 1
# save second for infect this block.
templab[nr][nc] = sec
q = tempq
if cnt_change == cnt_0:
result = sec - 1
if minSec > result:
minSec = result
# print("-------")
# for k in templab:
# print(*k)
if minSec != 1000000:
print(minSec)
else:
print(-1)
풀이 4
활성화된 바이러스가 숫자로 바뀌었으므로,
그 칸의 숫자가 max값을 구하는 데에 이용되지 않도록 처리해주어야 함.
line 54~55 참고.
추가로, 모든 빈칸에 바이러스가 퍼졌는지 계산하는 과정을 풀이 1과 같이 다시 반복문 안에 넣음. 다행히 TLE나지 않고 잘 진행.
드디어 AC!!!
from collections import deque
from itertools import combinations
import copy
# input
N, M = map(int, input().split())
lab = []
for _ in range(N):
lab.append(list(map(int, input().split())))
# delta row, delta col.
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]
# find 2 in laboratory / count 0 in lab / change numbers(wall, virus)
twos = []
cnt_0 = 0
for r, row in enumerate(lab):
for c, i in enumerate(row):
if i == 2:
twos.append([r, c])
lab[r][c] = "*"
elif i == 1:
lab[r][c] = "-"
elif i == 0:
cnt_0 += 1
# Combination - (len of twos) C (M) - find all combination of index.
start = list(combinations(twos, M))
# save Minimum Second to infect all blocks.
minSec = 1000000
def isAllInfected(inLab):
# function to know all blocks infected.
for row in inLab:
for c in row:
if c == 0:
return False
return True
# check if minSec = 0
if isAllInfected(lab):
print(0)
exit()
def check(inLab):
count0 = 0 # 0의 갯수 확인
maxCount = 0 # 최단 거리 계산
for two in twos:
inLab[two[0]][two[1]] = "*"
for i in range(N):
for j in range(N):
if inLab[i][j] == 0:
return -1
if inLab[i][j] != '*' and inLab[i][j] != '-':
maxCount = max(maxCount, inLab[i][j])
if count0 == 0:
return maxCount
# cycle of combinations
for s in start:
sec = 0
q = deque(s)
templab = copy.deepcopy(lab)
# BFS - one cycle (1 case)
while q:
sec += 1
tempq = deque()
# BFS - one cycle (1 sec)
while q:
r, c = q.popleft()
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
# check if wall / if virus already infected.
if N > nr >= 0 and N > nc >= 0 and (templab[nr][nc] == 0 or templab[nr][nc] == "*"):
tempq.append([nr, nc])
# save sec for infect this block.
templab[nr][nc] = sec
q = tempq
a = check(templab)
if a != -1 and minSec > a:
minSec = a
# print("-------")
# for k in templab:
# print(*k)
if minSec != 1000000:
print(minSec)
else:
print(-1)