[실버1] 18405번 : 경쟁적 전염

🛠 문제

https://www.acmicpc.net/problem/18405


👩🏻‍💻 해결 방법

바이러스 타입, 위치, 경과시간을 저장하기 위한 deque를 생성했다
sort를 통해 낮은 번호의 바이러스부터 전염되도록 하였다
bfs를 통해 바이러스를 전염시키고, 경과시간과 입력받은 S의 값이 같다면 while문을 종료했다

소스 코드

from collections import deque
n, k = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
S, X, Y = map(int, input().split())
virus = []

for i in range(n):
  for j in range(n):
    if data[i][j] != 0:
      virus.append([data[i][j], i, j, 0])
virus.sort()

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

q = deque(virus)
while q:
  virus_type, x, y, now = q.popleft()
  if now == S:
    break

  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < n:
      if data[nx][ny] == 0:
        data[nx][ny] = virus_type
        q.append([virus_type, nx, ny, now+1])

print(data[X-1][Y-1])

좋은 웹페이지 즐겨찾기