개요
🖱️ 문제 링크 : https://www.acmicpc.net/problem/17142
- 시간 제한 : 0.25 초
- 메모리 제한 : 512 MB
- 기출 : 삼성 SW 역량 테스트 기출 A형 문제지
문제
⌨️ 입력
첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.
둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다.
- 0 : 빈 칸
- 1 : 벽
- 2 : 바이러스를 놓을 수 있는 위치
- 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.
🖨️ 출력
연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다.
바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.
해결 방법
💡 문제 이해
삼성 코테 문제중 연구소 시리즈 마지막이다.
솔직히 연구소2 랑 문제가 똑같아보여서 처음에는 문제 잘못 들어온줄 알았다.
그런데 연구소2 랑 다른점이 있긴 있었다.
활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
이 문장 하나가 가져올 파장은 너무 컸다, 이해하는데 진짜 오래 걸렸고 결국 자력으로 못 풀었다..
포인트는 비 활성 바이러스도 결국은 바이러스다! 이다.
이게 무슨 개소리냐 하면 이 문제의 궁극적인 목표는 연구소의 '모든 빈칸'에 바이러스가 있게 되는 최소 시간을 구해라 이므로 비활성 바이러스가 활성 바이러스를 만나 활성화 된것은 최소 시간에 업데이트 하지 않는다는 소리다.
다시 말해 활성 바이러스가 이동한 결과 비활성 바이러스 칸과 맞닥뜨렸을 경우, 큐와 방문처리는 하되 최소 시간 반영은 하지 않는다.
time = max(time, visited[nx][ny])즉, 이 코드에 넣지 않는다는 소리다!
이걸 이해하는데 몇시간이 걸렸는지 ㅋㅋ;
자, 다시 정리하자면 연구소 2와 동일하나 마지막에 비활성화 바이러스만 남아있는 경우를 배제 해줘야한다.
즉 최소 시간 배열을 만들고 비활성화 바이러스가 있는 영역을 제외한 영역 을 차지하는데 걸린 시간을 찾아야한다.
그 이후의 풀이는 굉장히 쉽다! 시킨대로 구현하면 되거든요 ㅡㅡ
이전 연구소1 문제와 다른 점은 벽을 세우는 것이 아니고, 바이러스를 M개 선택해야하는 것이다.
바이러스의 선택 → DFS 경우의 수 : 조합 문제 (combinations 최고!)
바이러스의 확산 → 토마토 문제를 같이 조합해서 풀면 된다.
BFS 다 돌리고 나서 완탐 돌려서 벽이 아닌데 미 방문인 칸(= 바이러스에 감염되지 않은 칸) 이 있다면 리턴 값으로 무지막지하게 큰 값을 줘버리면 끝.
시간 제한이 0.25초로 평소보다 많이 작은데 완전 탐색을 해도 되나? 라는 생각도 했지만
조합(Combination) : 최악의 경우는 10C5 이므로 최대 경우의 수는 252회
연구소 탐색 : 연구소의 최대 크기는 50 X 50 이므로 최대 2500의 연산량
통상 파이썬에서는 1초에 대략 2천만회의 연산을 하니까?
이 문제를 풀기 위해서는 최대 630,000회(252 * 2500)의 연산량밖에 필요로 하지 않으므로
조합 + BFS만으로 충분한 연산이 가능하지 않을까 라는 생각을 했다.
Python Code
# 백준 17142 연구소 3
import sys
from collections import deque
from itertools import combinations
read = sys.stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
virus = []
answer = int(1e9)
def BFS():
visited = [ [-1]*N for _ in range(N) ]
# 최소 시간
time = 0
for x, y in queue:
visited[x][y] = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
# 빈 칸이며 미 방문 상태
if lab[nx][ny] == 0 and visited[nx][ny] == -1:
visited[nx][ny] = visited[x][y] + 1
queue.append([nx,ny])
time = max(time, visited[nx][ny])
# 비 활성 바이러스를 만남
# 원래 바이러스가 있던 걸 활성화 시키는 것이므로 시간에는 반영이 안됨.
# 비 활성 바이러스도 바이러스다!
elif lab[nx][ny] == 2 and visited[nx][ny] == -1:
visited[nx][ny] = visited[x][y] + 1
queue.append([nx,ny])
# BFS가 끝난 이후 바이러스에 감염되지 않은 빈칸이 존재하는 경우
for i in range(N):
for j in range(N):
# 벽이 아닌데 미 방문인 칸이 있는 경우 = 바이러스에 감염되지 않은 칸이 있다
if lab[i][j] != 1 and visited[i][j] == -1:
return int(1e9)
return time
# 연구소의 크기, 놓을 수 있는 바이러스의 수
N,M = map(int,read().split())
lab = [ list(map(int, read().rstrip().split())) for _ in range(N) ]
for i in range(N):
for j in range(N):
if lab[i][j] == 2:
virus.append([i,j])
for virus_list in combinations(virus,M):
queue = deque()
for virus_x, virus_y in virus_list:
queue.append([virus_x, virus_y])
answer = min(BFS(), answer)
if answer == int(1e9):
print(-1)
else:
print(answer)왜 못풀었는가?
요즘들어 문제 이해하는데 시간이 너무 오래걸린다. 계속 PS 공부하는데 왜 이해력이 안늘지?(바보라서 미안해..) 할 수도 있는데 앞서 만난 문제들과 비슷하다고 생각이 들면 문제를 제대로 읽지 않고 저번에 푼 문제처럼 풀어버린다.
그래서 WA 받은 뒤에 문제를 다시 읽고 있으니 시간이 2배로 걸릴 수 밖에..
마치 수능 국어 풀던 나를 보는거 같다.
맘대로 해석한 뒤 -> 문제 풀고 -> 틀리고 나서 -> 아! 잘못 이해했구나!
무한 루프에 빠지는 것 ㅋㅋ
이전 문제의 경험을 대입하는것은 좋으나 너무 맹신하지 말자 제발!
조금만 더 고민해봤으면 풀었을거 같기도 하고 속상하다 ㅜ
