이번 문제는 BFS를 통해 해결하였다. 처음에는 벽에서마다 BFS를 통해 주변을 탐색하도록 하였는데 시간초과가 발생하였다. 그 이유는 그렇게 되면 같은 통로를 여러번 탐색하기 때문이었다. 그래서 통로들의 그룹을 BFS를 통해 만들어 딕셔너리에 정보를 저장하고, 각 벽에서 4방향을 확인하여 인접하는 그룹들의 크기만큼을 더하도록 하였다.

Code

from collections import deque, defaultdict
n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
answer = [['0' for _ in range(m)] for _ in range(n)]
groups = defaultdict(int)
num = 2
def make_groups(y, x):
    q = deque()
    q.append((y, x))
    grid[y][x] = str(num)
    cnt = 1
    while q:
        cy, cx = q.popleft()
        for i in range(4):
            ny, nx = cy+dy[i], cx+dx[i]
            if 0 <= ny < n and 0 <= nx < m and grid[ny][nx] == '0':
                grid[ny][nx] = str(num)
                cnt += 1
                q.append((ny, nx))
    return cnt
for i in range(n):
    for j in range(m):
        if grid[i][j] == '0':
            groups[str(num)] = make_groups(i, j)
            num += 1
        if grid[i][j] == '1':
            answer[i][j] = '1'
for i in range(n):
    for j in range(m):
        if grid[i][j] == '1':
            tmp = []
            for d in range(4):
                ni, nj = i+dy[d], j+dx[d]
                if 0 <= ni < n and 0 <= nj < m:
                    if grid[ni][nj] != '1' and grid[ni][nj] not in set(tmp):
                        tmp.append(grid[ni][nj])
            for group in tmp:
                answer[i][j] = str((int(answer[i][j])+groups[group])%10)
for i in range(n):
    print(''.join(answer[i]))