일본은행(G4) 1888 다이

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