BOJ - 18405 - 경쟁적 전염

Updated:

import sys
from collections import deque

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

def BFS(maps, dq, N):
    S, X, Y = map(int, sys.stdin.readline().split())
    time = 0
    while time < S:
        for _ in range(len(dq)):
            x, y, w = dq.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if 0 <= nx < N and 0 <= ny < N:
                    if maps[nx][ny] == 0:
                        maps[nx][ny] = w
                        dq.append((nx, ny, w))

        time += 1

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

def solution():
    N, K = map(int, sys.stdin.readline().split())
    maps = []
    virus = []
    for _ in range(N):
        maps.append(list(map(int, sys.stdin.readline().split())))

    for i in range(N):
        for j in range(N):
            if maps[i][j] != 0:
                virus.append((i, j, maps[i][j]))
    virus = deque(sorted(virus, key=lambda x:x[2]))
    BFS(maps, virus, N)

solution()

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

Categories:

Updated:

Leave a comment