# BOJ - 10711 - 경쟁적 전염

Updated:

``````import sys
from copy import deepcopy
from collections import deque

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

def Check(x, y, H, W, sandCastle):
waveSum = 0
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < H and 0 <= ny < W:
if sandCastle[nx][ny] == '.':
waveSum += 1

if waveSum >= int(sandCastle[x][y]):
return True
else:
return False

def BFS(sandCastle, visit, dq, H, W):
time = 0
while dq:
for _ in range(len(dq)):
x, y = dq.popleft()
sandCastle[x][y] = '.'
dq.append((x, y))

for _ in range(len(dq)):
x, y, = dq.popleft()
for k in range(8):
nx, ny = x + dx[k], y + dy[k]
if not visit[nx][ny]:
if sandCastle[nx][ny] != '.':
if Check(nx, ny, H, W, sandCastle):
dq.append((nx, ny))
visit[nx][ny] = True

time += 1
print(time)

def solution():
dq = deque()
sandCastle = []
visit = [[False for _ in range(W)] for _ in range(H)]
for _ in range(H):

for i in range(H):
for j in range(W):
if sandCastle[i][j] == '.':
continue
if int(sandCastle[i][j]) == 9:
continue
if Check(i, j, H, W, sandCastle):
dq.append((i, j))
visit[i][j] = True

BFS(sandCastle, visit, dq, H, W)

solution()
``````

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

Categories:

Updated: