문제 설명

->링크<-

해결 방법

시간마다 BFS를 해줘야하고 바이러스의 번호에 따라서 우선순위가 정해진다. 그렇다면 우선순위를 1. 시간 2. 번호순으로 우선순위큐로 넣어준다면 간단하게 풀 수 있게된다. 이때 시간이 S초를 넘어간다면 더이상 BFS탐색을 하지 않으면 깔끔하게 구현 할 수 있다.

해답 코드

import sys
import heapq
input = sys.stdin.readline

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
N, K = map(int, input().split())
matrix = []
for i in range(N):
  matrix.append(list(map(int, input().split())))

s, y, x = map(int, input().split())

#BFS로 바이러스 증식
#우선순위 큐
HQ = []
#초기 값들을 우선순위 큐에 push
for i in range(N):
  for j in range(N):
    if matrix[i][j] >= 1 and matrix[i][j] <= K:
      heapq.heappush(HQ, (0, matrix[i][j], i, j))
#BFS시작
while len(HQ) > 0:
  time, num, Y, X = heapq.heappop(HQ)
  #네방향으로 퍼뜨리기
  for i in range(4):
    curY = Y + dy[i]
    curX = X + dx[i]

    #시간을 초과 하는지 확인
    #경계 안에 있는지 확인
    if time < s and curY >= 0 and curY < N and curX >= 0 and curX < N:
      if matrix[curY][curX] == 0:
        matrix[curY][curX] = num
        heapq.heappush(HQ, (time+1, num, curY, curX))

print(matrix[y-1][x-1])

걸린시간

다른사람의 코드를 보고난 후

나랑 완전다른 해결방법이 잇었다!!!
BFS를 전부 탐색하고 갱신을 할때마다.
virus라는 리스트에 바이러스 넘버, 좌표를 넣어줘서
sort를 해주면 바이러스 넘버를 우선적으로 정렬하여 목표좌표의 값중 제일 앞에있는것을 꺼내면 된다.

힙을 대부분 쓰질 않았다.

왜냐하면 초기에 0초일때 바이러스들을 큐에넣고 정렬만 해주면 단순히
해결되는 문제였다. 어차피 큐에순서대로 처리를 하므로 우선순위큐를 굳이!! 사용할 필요는 없었다.