이해

• N x N 시험관에 1번부터 K번까지의 바이러스들이 존재할 수 있다.
• 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나가며, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.
• 증식 과정에서 특정한 칸에 이미 바이러스가 존재한다면, 그 곳에 다른 바이러스가 들어갈 수 없다.
• s초가 지난 후에 (x, y)에 존재하는 바이러스의 번호를 출력하라.

계획

• 시험관에 있는 바이러스 중 번호가 작은 순서대로 바이러스의 위치와 몇 초 지났는 지(0초)에 대한 정보를 queue에 넣어준다.
• bfs 알고리즘을 사용하여 시험관을 탐색한다. 처음에 시험관에 존재하는 바이러스의 위치를 바이러스 번호가 작은 순서대로 queue에 넣어주었기 때문에 매 초마다 번호가 낮은 종류의 바이러스부터 증식하도록 구현할 수 있다.
• queue에서 꺼낸 바이러스가 증식한 시간이 s초가 지난 경우 시험관의 (x, y) 위치에 있는 번호를 출력한다.

실행

import sys
from collections import deque

input = sys.stdin.readline

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

n, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
s, x, y = map(int, input().split())


def bfs(arr, queue):

    while queue:
        num, sec, _x, _y = queue.popleft()
        if sec == s:
            break
        for i in range(4):
            nx, ny = _x + dx[i], _y + dy[i]
            if 0 <= nx <= n - 1 and 0 <= ny <= n - 1 and arr[nx][ny] == 0:
                arr[nx][ny] = num
                queue.append((num, sec + 1, nx, ny))


queue = []

for i in range(n):
    for j in range(n):
        if board[i][j] != 0:
            queue.append((board[i][j], 0, i, j))
queue.sort()
queue = deque(queue)

bfs(board, queue)
print(board[x - 1][y - 1])

개선

• 딱히 없다.

회고

• 쉬웠고, 잘 푼 것 같다.