[백준/18405][Python] 경쟁적 전염

문제

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

18405번: 경쟁적 전염

풀이

1. 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.라는 조건을 잘봐야한다. 큐에 들어갈 때 바이러스 번호를 기준으로 정렬을 한 다음 넣어주면 매 초마다 큐에 바이러스 번호가 작은 순서대로 남게 된다.

그리고 매 초마다 큐에 들어오는 칸 수만큼 반복해서 상하좌우 검사를 해준다. 

이 문제를 예시로

- 맨 처음에는 3개의 바이러스가 큐 안에 들어있다. (1,0,0), (2,0,2), (3,2,0) - 순서대로 바이러스 번호, x좌표, y좌표를 뜻한다.
- 이후 1이 pop되면서 하, 우 방향에 1을 전염시키고 큐에 추가된다. 2가 pop되면서 하 방향에 2를 전염시키고, 3이 pop되면서 우 방향에 3을 전염시킨다. 그러면 1초 뒤에는 큐에 (1,1,0), (1,0,1), (2,1,2), (3,2,1)가 새로 담기게 된다. 이처럼 자동으로 번호가 작은 수부터 큐에 담기게 된다. 

- 다른 풀이들을 보면 주로 초를 큐에 넣을 때 같이 추가해서 변수로 가지고 다니던데, 나는 그 방식보다 큐의 길이만큼 반복하는 방식을 선택해주었다.

코드

import sys
from collections import deque
read = sys.stdin.readline
############변수 입력 받기############
n,k = map(int, read().split())
board = [list(map(int,read().rstrip().split())) for _ in range(n)]
s,x,y = map(int, read().split())
####################################
dx = [-1,0,1,0]
dy = [0,-1,0,1]
data = []
for i in range(n):
  for j in range(n):
    if board[i][j] != 0:
      data.append((board[i][j],i,j))

data.sort()
dq = deque(data)

sec = 0
while dq:
  if sec == s:
    break
  for _ in range(len(dq)): #매번 새로 들어오는 칸의 수만큼 반복
    vir, xx, yy = dq.popleft()
    for dir in range(4):
      nx = xx + dx[dir]
      ny = yy + dy[dir]
      if nx<0 or ny<0 or nx>=n or ny>=n:
        continue
      if board[nx][ny] != 0:
        continue
      board[nx][ny] = vir
      dq.append((vir,nx,ny))
  sec+=1

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