[Baekjoon]18405. 경쟁적 전염 (Gold_5) 2024/4/9

문제 제목	정답률	난이도
경쟁적 전염	30%	Gold_5

 

문제요약
정사각형 시험관 길이 N, 바이러스 종류 K가 첫 번째 줄에 주어진다(바이러스는 1~K번까지 있다고 가정한다.

1~N+1줄에는 시험관에 있는 상태(바이러스가 있으면 바이러스 종류, 없으면 0)가 주어진다.

N+2 줄에는 S, X, Y가 주어질때
조건 1) 1 <=N <=200, 1 <=K <=1000, 0 <=S <=10000, 1 <=X, Y <=N 

조건 2) 바이러스는 1초마다 상, 하, 좌, 우 빈 공간에 침투한다.(이미 바이러스가 존재하는 곳에는 침투하지 못한다)

조건 3) 바이러스 종류의 숫자가 작은 순서대로 우선 침투권을 가진다

S초 후에 정사각형 시험관 X번째 row Y번째 col의 상태를 반환하여라
 

풀이

Step1. 바이러스 관점에서 생각할지 시험관 관점에서 생각할지 판단

• 바이러스 관점에서 생각할 경우 -> 1초마다 상태 업데이트 필요
• 시험관 관점에서 생각할 경우 -> 주위의 바이러스 찾아야 함

Step2. 직관적으로 바이러스 관점에서 생각해 보자

• 바이러스가 들어있는 곳의 정보를 받아서
• 1초마다 location update
• 바이러스는 인덱스가 작은 게 우선순위를 가지니까 -> heapq 이용하자
  • 더 자세히 기술하면, 시간이 적을수록 인덱스가 작을수록 우선순위를 가지고, 현재 위치에 대한 정보가 있어야 하므로 heapq에 [second, virus_idx, row, col]이런 식으로 삽입하면 좋을 것 같다.
• 최대 O(바이러스가 있는 location 수*Second)이니까 K*10000 (K <=40000) 시간복잡도를 위해 더 빨리 끝낼 수 있는 조건이 필요)
  • XY위치에 바이러스가 삽입(이미 삽입된 곳에는 침투하지 못하니까) : location [X-1][Y-1]==0
  • 새로 삽입된 바이러스가 없는 경우 : virus_q

 

코드

import sys
import heapq

f = sys.stdin.readline
N, K= map(int, f().split())

location=[]
virus_q=[]
for row in range(N):
    location.append(list(map(int, input().split())))
    for col in range(N):
        if location[row][col]!=0:
            heapq.heappush(virus_q, [0, location[row][col], row, col]) #second, virus_idx, row_idx, col_idx

f = sys.stdin.readline
S, X, Y= map(int, f().split())

while virus_q and virus_q[0][0] <= (S-1):
    if location[X-1][Y-1] != 0:
        break
    now = heapq.heappop(virus_q)
    four = [[now[2]-1, now[3]], [now[2]+1, now[3]],[now[2], now[3]-1], [now[2], now[3]+1]]
    for row_idx, col_idx in four:
        if row_idx >= 0 and row_idx < N and col_idx >= 0 and col_idx < N:
            if location[row_idx][col_idx] == 0:
                location[row_idx][col_idx] = now[1]
                heapq.heappush(virus_q, [now[0]+1, now[1], row_idx, col_idx])
print(location[X-1][Y-1])