[백준] 18405 경쟁적 전염

📖 문제

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

💻 내 코드

import sys
from collections import  deque
N, K = map(int, sys.stdin.readline().split())
board = []
q = []

for i in range(N):
    virus = list(map(int,sys.stdin.readline().split()))
    board.append(virus)
    for j in range(N):
        if virus[j] !=0: # 바이러스가 존재하는 위치
            q.append((virus[j], i, j))

S, X, Y = map(int,sys.stdin.readline().split())

q.sort() # 번호가 낮은 종류부터 증식하기 때문에 sort
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs():
    cnt = 0
    queue = deque(q)

    while queue:
        if cnt == S or not queue:
            break
        for _ in range(len(queue)):
            num, x, y = queue.popleft()
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]

                if 0<=nx<N and 0<=ny<N:
                    if board[nx][ny]==0:
                        board[nx][ny] = num
                        queue.append((num,nx, ny))
        cnt+=1
    return board[X - 1][Y - 1]

print(bfs())

💡 풀이

• BFS 이용
• 번호가 낮은 바이러스부터 증식한다고 했으므로 바이러스의 위치를 담은 리스트를 sort한 뒤 bfs 진행하게 되면 항상 낮은 종류의 바이러스가 먼저 움직이게 된다
• bfs 탐색을 하면서 움직이려는 위치가 0이라면 증식 가능