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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net




from collections import deque

def dfs(x, y, idx):

    q = deque()

    q.append((x, y))

    graph[x][y] = idx

    cnt_block = 0 #벽돌의 갯수


    while q:

        a, b = q.popleft()

        cnt_block += 1

        for i in range(4):

            na, nb = a + dx[i], b + dy[i]

            if 0 <= na < N and 0 <= nb < M and graph[na][nb] == 0:

                graph[na][nb] = idx

                q.append((na, nb))

    return cnt_block



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

N, M = map(int, input().split())

result = [0] * (N * M) #  [idx에서 idx개수]


graph = []

for _ in range(N):

    graph.append(list(map(int, input().strip())))


result2 = [[0] * M for _ in range(N)]  #결과 graph


idx=1


for i in range(N):

    for j in range(M):

        if graph[i][j] == 0:  #방문안햇을경우?

            idx += 1

            result[idx] = dfs(i, j, idx)  #몇개있는지 조지고  [i,j]를 idx



for i in range(N):

    for j in range(M):

        if graph[i][j] == 1:

            count = 1

            check = [0] * (N * M)

            for z in range(4):

                na, nb = i + dx[z], j + dy[z]

                if 0 <= na < N and 0 <= nb < M:

                    if graph[na][nb] != 0 and check[graph[na][nb]]==0:

                        check[graph[na][nb]]=1

                        count += result[graph[na][nb]]

            result2[i][j] = count % 10


for i in range(N):

    a = "".join(map(str, result2[i]))

    print(a)