[백준] 17142. 연구소 3 - 파이썬

[Gold III]

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고

www.acmicpc.net

이 문제는... 사실 토마토나, 백조의 호수 같은 문제와 유사한 문제였으나, 시간이 조금 걸렸다.

문제를 푸는 핵심은, '비활성화된 바이러스 또한 전염이 진행될 수 있도록 처리할 것.'

그리고, '비활성화된 바이러스가 활성화되는 것은 최소 시간을 측정하는 데에 고려하지 않아야 할 것.'

이것들을 유념하며 문제를 풀어 나가야 한다.

풀이 1

일단 BFS 문제라는 것은 보자마자 알 수 있었다.

다만, 시간제한이 좀 빠듯할 것 같다는 생각이 들었는데...

바이러스를 놓을 수 있는 칸은 총 (M~10)개가 있고, 놓을 수 있는 바이러스의 개수가 M(1~10)개.

이 경우들을 모두 Brute-Force로 따져서 하나하나 BFS를 돌려가며 계산해보는 방법밖엔 없어서였는데,

막상 최대 갯수를 계산해 보면 ₁₀C₅이므로 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)

풀이 1
풀이 2
풀이 3
풀이 4

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

[백준] 17142. 연구소 3 - 파이썬

풀이 1

풀이 2

풀이 3

풀이 4

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

	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)