[python] 백준 18405번 : 경쟁적 전염 (BFS)

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

18405번: 경쟁적 전염

 

 

1. 시간초과 발생한 코드 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
time, x, y = map(int, input().split())

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


def contagious(tmp, x, y):
    num = tmp[x][y]

    for m in range(4):
        xx = x + dx[m]
        yy = y + dy[m]
        if 0 <= xx < n and 0 <= yy < n and tmp[xx][yy] == 0:
            tmp[xx][yy] = num


tmp = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        tmp[i][j] = board[i][j]
t = 0
while True:
    t += 1
    if t > time:
        break
    # print('time is..', t,'->',t+1)
    for num in range(1, k + 1):
        for i in range(n):
            for j in range(n):
                if board[i][j] == num:
                    contagious(tmp, i, j)

    for i in range(n):
        for j in range(n):
            board[i][j] = tmp[i][j]

print(board[x - 1][y - 1])

 

 

2. 정답인 코드 

from collections import deque
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
graph = []
data = []
for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] != 0:
            data.append((graph[i][j], 0, i, j))

# 바이러스 크기순으로 정렬 
data.sort()
q = deque(data)

time, a, b = map(int, input().split())

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

while q:
    virus, t, x, y = q.popleft()
    if t == time:
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<n and graph[nx][ny] == 0:
            graph[nx][ny] = virus
            q.append((virus, t+1, nx, ny))

print(graph[a-1][b-1])