bfs인데 bfs는 확인용이라 곰팡이를 펴는 과정이 중요한 것 같습니다.
시간 초과가 계속되었지만 불필요한 부분을 제거한 후 속도가 빨라져 for 문이 액세스를 반환하지 않습니다.
그리고 모두 0일에 접속하는 경우도 있습니다.
이 부분에서 막혔는데 0일에 판단하고 첫 줄에 if 문이 있고 끝납니다.
더보기
# 곰팡이가 피어있는 곳은 그 곰팡이의 자라는 속도
# 어느 곰팡이의 자라는 속도가 k라면, 하루가 지났을 때 그 곰팡이가 피어있던 자리를 중심으로 2k+1행 2k+1열의 격자에 같은 종의 곰팡이가 번진다는 의미이다.
# 만약 서로 다른 종의 곰팡이가 같은 칸에 번져 오면, 자라는 속도가 빠른 곰팡이가 그 칸을 차지한다.
# 곰팡이가 한 덩어리가 되기까지 걸리는 시간을 하루 단위로 출력한다.
from copy import deepcopy
from collections import deque
N, M = map(int, input().split())
pan = (list(map(int, input())) for _ in range(N))
def check():
'''
덩어리를 확인할 함수
'''
number = 0
visited = ((0 for _ in range(M)) for _ in range(N))
for n in range(N):
for m in range(M):
if not visited(n)(m) and pan2(n)(m):
number += 1
if number > 1: # 군집이 한 개가 넘어가면 바로 끊어줌
return False
q = deque(((n, m)))
visited(n)(m) = 1
while q:
x, y = q.popleft()
for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):
nx, ny = x + dx, y + dy
if N > nx >= 0 and M > ny >= 0 and not visited(nx)(ny) and pan2(nx)(ny):
visited(nx)(ny) = 1
q.append((nx, ny))
return True # 군집이 한 개 이하라면 여기까지 옴
def bfs(i, j, velo):
'''
속도로 퍼트릴 함수
속도 이하라면 잡아먹는다.
'''
for n in range(i-velo, i+velo+1):
for m in range(j-velo, j+velo+1):
# print(n, m)
if N > n >= 0 and M > m >= 0 and pan(n)(m) < velo:
# 속도가 작은 경우에만 퍼지기때문에 같은경우 visit에 체크되지 않는다.
# 그래서 가장자리 부분만 bfs함수가 실행된다.
pan2(n)(m) = velo
visit(n)(m) = 1
ans = 0
while 1:
pan2 = deepcopy(pan)
if not ans and check(): # 처음에도 판단을 한 번 해야하는데 바로 조져준다
print(ans)
break
ans += 1 # 그렇지 않으면 하루 경과이다
visit = ((0 for _ in range(M)) for _ in range(N)) # visit을 해주지 않으면 예제와 조금 달라진다
for p in range(N):
for q in range(M):
if pan(p)(q) and not visit(p)(q): # 숫자가 있고 방문하지 않았다면
visit(p)(q) = 1
bfs(p, q, pan(p)(q))
if check():
print(ans)
break
pan = pan2