[백준] 18405번 경쟁적 전염 - Python

이번에 해결해 볼 문제는 백준에 있는 경쟁적 전염이다.

---

문제 설명

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

문제 아이디어

• 바이러스는 상하좌우로 퍼져나가므로 BFS를 떠올릴 수 있다.
• 구현할 수 있는 방법
  • 우선순위가 존재하므로 우선순위를 설정하여 우선순위 큐를 구현
  • 기본적인 큐에 우선순위대로 바이러스를 삽입하도록 구현

문제 해결 코드

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
test = [list(map(int, input().split())) for _ in range(n)] # 시험관
s, x, y = map(int, input().split())
x, y = x-1, y-1

# BFS
from collections import deque
q = deque([]) # 바이러스가 퍼져나가는 순서
virus = [[] for _ in range(k+1)]

# 우선순위를 주기위해 바이러스 번호 순서대로 Queue에 삽입
for i in range(n):
    for j in range(n):
        if test[i][j] != 0:
            virus[test[i][j]].append((i, j))

for v in virus:
    for i in v:
        q.append(i)

dx = [-1,1,0,0]
dy = [0,0,-1,1]
for _ in range(s):
    # 현재 있는 바이러스를 상하좌우로 한 칸씩 전염하기 위해 현재 있는 바이러스 개수 카운트
    virus_count = len(q)
    for _ in range(virus_count):
        vx, vy = q.popleft()
        for i in range(4):
            nx, ny = vx+dx[i], vy+dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if test[nx][ny] == 0:
                    test[nx][ny] = test[vx][vy] # 전염
                    q.append((nx, ny))
print(test[x][y])