소스 코드 :
from collections import deque
n, k = map(int, input().split())
data = []
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
for j in range(n):
if graph[i][j] > 0:
# 바이러스 타입, x좌표, y좌표 순
data.append((graph[i][j], i, j, 0))
s, x, y = map(int, input().split())
# 상, 하, 좌, 우 방향 리스트
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
data.sort()
q = deque(data)
while q:
virusNum, a, b, time = q.popleft()
# 시간 일치할 경우, 탈출
if time == s:
break
# 작은 번호부터 순서대로 바이러스 전염 진행
for i in range(4):
na = a + dx[i]
nb = b + dy[i]
if 0 <= na and na < n and 0 <= nb and nb < n and graph[na][nb] == 0:
graph[na][nb] = virusNum
q.append((virusNum, na, nb, time + 1))
print(graph[x -1][y - 1])
'''
시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
Q. 번호별로 좌표의 위치를 어떻게 파악할 것인가?따로 리스트를 만들어서 관리할 건가?
A. 반복문을 돌리면서 확인하는 것은 1초 / 256MB의 제한 조건에서 시간복잡도 상의 문제로 시간 초과가 발생할 것이므로 별도로 관리해야 할 것이다.
--> 큐를 이용해서 입력받은 값 관리 // 단, 바이러스타입과 시간도 해당 큐에서 튜플을 통해서 같이 관리하여야 함. time은 변수를 따로 선언해서 진행할 수 없었음
'''- 문제 출처 : https://www.acmicpc.net/problem/18405
- 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.
