18405: 경쟁적 전염

풀이 시간

• 25m

구현 방식

• 매 초마다 1~K까지 순서대로 전염되도록 구현한다면 최악의 경우 N * N * S = 200 * 200 * 10000으로 시간초과가 발생한다

• 따라서 queue에 현재 몇 초인지를 넣어주어 (s == S 경우 break) while문 한 번에 끝나도록 구현해주었다

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def infection():
    queue = []
    for x in range(N):
        for y in range(N):
            if board[x][y] != 0:
                queue.append((board[x][y], 0, x, y))
    queue.sort(); queue = deque(queue)

    while queue:
        k, s, x, y = queue.popleft()
        if s == S:
            break
        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] = k
                    queue.append((k, s+1, nx, ny))


N, K = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))
S, X, Y = map(int, sys.stdin.readline()[:-1].split()); X -= 1; Y -= 1

infection()

print(board[X][Y])

결과