백준 16946 벽 부수고 이동하기 4

from collections import deque

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

n, m = map(int, input().split())
g = [list(map(int, input())) for _ in range(n)]

# 0끼리 그룸을 만든다
check = [[-1] * m for _  in range(n)]

groupn = 0
group = []
for i in range(n):
    for j in range(m):
        if g[i][j] == 0 and check[i][j] == -1:
            q = deque()
            q.append((i, j))
            check[i][j] = groupn
            cnt = 1
            while q:
                x, y = q.popleft()
                for k in range(4):
                    nx, ny = x +dx[k], y + dy[k]
                    if nx < 0 or ny < 0 or nx >= n or ny >= m:
                        continue
                    if g[nx][ny] == 0 and check[nx][ny] == -1:
                        check[nx][ny] = groupn
                        q.append((nx, ny))
                        cnt += 1
            group.append(cnt)
            groupn += 1

ans = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if g[i][j] == 1:
            ans[i][j] += 1
            plus = []
            for k in range(4):
                ni, nj = i + dx[k], j + dy[k]
                if ni < 0 or nj < 0 or ni >= n or nj >= m:
                    continue
                if g[ni][nj] == 0:
                    plus.append(check[ni][nj])
            plus = set(plus)
            plus = list(plus)
            for k in plus:
                ans[i][j] += group[k]
            ans[i][j] %= 10

for i in range(n):
    print(*ans[i], sep='')

무턱대고 bfs 하나하나씩 돌리면 시간 초과 (n 과 m 이 매우 큼)
0개들을 그룹을 지어서 한 1에 인접한 0개들 그룹 속 인접한 0의 갯수를 다 더해줌