[BOJ-18405] 경쟁적 전염

문제

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

18405번: 경쟁적 전염

내 풀이

바이러스가 있는 지점에서부터 BFS 수행, 이 떄 낮은 번호부터 시작하도록 정렬하여 시작할 것

 

from collections import deque
 
n, k = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))
s, x_r, y_r = map(int, input().split())
 
len_col = len(board[0])
 
# moving
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
 
q = []
for x in range(n):
    for y in range(len_col):
        if board[x][y] != 0:
            q.append((x, y, board[x][y], 0))
q = sorted(q, key=lambda x : x[2])
 
# BFS
 
q = deque(q)
depth = 0
while q:
    x, y, v, depth = q.popleft()
    if depth == s:
        break
 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= len_col:
            continue
        else:
            if board[nx][ny] == 0:
                board[nx][ny] = v
                q.append((nx, ny, v, depth + 1))
 
print(board[x_r-1][y_r-1])