728x90
연구소3
- 링크:https://www.acmicpc.net/problem/17142
- 난이도:골드 3
- 분류: 그래프이론, 브루트포스 알고리즘, 그래프 탐색, BFS
- 직접 푼 여부: X
풀이 노트
- "연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. "
- 모든 칸에 바이러스가 있으면 된다. 굳이 다 활성 바이러스일 필요는 없다.
- 아래 velog에서 잘 정리해주셔서 참고하여 문제를 풀었습니다.
- 풀이 순서는
- 1. 활성화할 바이러스를 m개 고른다. itertools를 쓰지 않고 dfs사용. (select_virus)
- 2. 다 고르면, 해당 바이러스들을 확산 시킨다. bfs사용 (defussion)
- 간단한 변수명을 제 취향에 맞게 바꾸고, 이해를 하며 주석을 추가하였습니다. 그리고 바이러스를 고르는 def에서 list를 def에서 넘겨받지 않고, global로 설정해서 푼 풀이가 아래 정답코드 입니다. 원본 풀이가 궁금하신분은 아래 링크를 확인해주시기 바랍니다!
- 참고: https://velog.io/@7h13200/Python%EB%B0%B1%EC%A4%8017142%EB%B2%88-%EC%97%B0%EA%B5%AC%EC%86%8C3
정답 코드 💻
# 연구소 3
# 참고: https://velog.io/@7h13200/Python%EB%B0%B1%EC%A4%8017142%EB%B2%88-%EC%97%B0%EA%B5%AC%EC%86%8C3
import sys
from copy import deepcopy
input = sys.stdin.readline
lab =[] # map
virus =[] # [좌표r,c, 확산에 걸린 시간]
n,m = map(int, input().split()) # n: 크기, m: 바이러스 개수
# 빈칸의 개수 (바이러스가 모두 확산되었는지 판단하기 위해서)
countnull =0
for i in range(n):
a =list(map(int, input().split()))
for j in range(n):
if a[j] ==2:
virus.append([i,j,0])
elif a[j] ==0:
countnull +=1
lab.append(a)
mintime = int(10e9)
# dfs : 바이러스중 활성화 시킬 바이러스를 고르는 dfs
# 코테가 아니라면, itertools combinations이 더 편하겠지만, 코테는 이를 사용못하니까! dfs로!
def choosevirus(depth, start):
# 활성화 시킬 바이러스를 다 골랐으면 확인
global select
if depth ==m:
vdeffusion(deepcopy(select)) # 바이러스 확산시키기
return
for i in range(start, len(virus)):
select.append(virus[i])
choosevirus(depth+1, i+1)
select.remove(virus[i])
dc = [-1,0,1,0]
dr= [0,-1,0,1]
# 바이러스 확산!
def vdeffusion(select):
global mintime
temptime =0
virus_count =0
temp_lab = deepcopy(lab)
# bfs - 확산
while select:
r,c,time = select.pop(0)
temp_lab[r][c] =3 #활성으로 변경
if virus_count == countnull:
# 빈칸이 다 채워짐 (확산 다 됨)
mintime = min(mintime, temptime)
return
if time >= mintime:
# 지금 걸린시간이 min시간보다 길어지면, 어차피 답아니니까 return
#temptime: 이번에 걸린 최대시간 - 이게 최대시간이 될 수 있는 이유는 select를 append할 때
# 즉, choosevirus와 defussion에서 time이 높아지는 순으로 append를 하였기 때문에 마지막이 가장 높은 것임
return
# 좌상우하 확산
for dir in range(4):
nr = r + dr[dir]
nc = c + dc[dir]
if (0<=nr<n) and (0<=nc<n):
# 변화가 일어나는 곳 1)빈칸, 2)비활성 바이러스 있는 곳
if temp_lab[nr][nc] ==0:
# 1) 빈칸이면, 바이러스 개수하나 더 늘었음 (원래 빈칸이였던 것이 다 바이러스가 되면 끝이니까)
virus_count +=1
temp_lab[nr][nc] =3 # 활성바이러스
select.append([nr, nc, time+1]) # 활성바이러스 생겼으니까 이것도 확산 됨
temptime = time +1
elif temp_lab[nr][nc] ==2:
temp_lab[nr][nc] =3
select.append([nr, nc, time+1])#활성바이러스가 되었으니까 이것도 확산 됨
# main 문
select =[]
select_virus(0,0)
# 정답출력
if mintime ==int(10e9):
#변함이 없다면 (확산 다 안됨)
print(-1)
else:
print(mintime)
728x90
'취준! ✒ > 삼성' 카테고리의 다른 글
[코테준비] 11. 백준- 주사위 윷놀이 (17825) python "삼성 SW 역량 테스트 기출 문제" (0) | 2023.09.25 |
---|---|
[코테준비] 10. 백준- 게리맨더링 2 (17779) python "삼성 SW 역량 테스트 기출 문제" (0) | 2023.09.24 |
[코테준비] 8. 백준- 미세먼지 안녕! (17144) python "삼성 SW 역량 테스트 기출 문제" -작성중 (0) | 2023.09.21 |
[코테준비] 7. 백준- 나무 재테크(16235) python "삼성 SW 역량 테스트 기출 문제" (2) | 2023.09.20 |
[코테준비] 6. 백준- 경사로(14890) python "삼성 SW 역량 테스트 기출 문제" (0) | 2023.09.17 |