우주의 IT 소행성

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

from collections import deque
n, m = map(int, input().split())
check = [[False] * m for _ in range(n)]
a = [list(map(int, list(input()))) for _ in range(n)]
group = [[0] * m for _ in range(n)]
group_size = []
group_number = 1
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs(n1, n2):
    queue = deque()
    queue.append((n1, n2))
    check[n1][n2] = True
    group[n1][n2] = group_number
    count = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if a[nx][ny] == 0 and not check[nx][ny]:
                    check[nx][ny] = True
                    queue.append((nx, ny))
                    group[nx][ny] = group_number
                    count += 1
    group_size.append(count)


for i in range(n):
    for j in range(m):
        if not check[i][j] and a[i][j] == 0:
            bfs(i, j)
            group_number += 1


for i in range(n):
    for j in range(m):
        if a[i][j] == 0:
            print(0, end='')
        else:
            near = set()
            for k in range(4):
                nx, ny = i + dx[k], j + dy[k]
                if 0 <= nx < n and 0 <= ny < m:
                    if a[nx][ny] == 0:
                        near.add(group[nx][ny])
            ans = 1
            for g in near:
                ans += group_size[g - 1]
            print(ans % 10, end='')
    print()

일단 맨 처음 빈 칸을 모두 그룹지어 그 개수를 구해줌.

벽을 비웠을 때 인접한 칸이 미리 만들어 둔 빈 칸 그룹에 포함된다면

그 그룹의 수 + 자기 자신을 더해주면 되는데

bfs는 한번만 돌려주면 됨(처음 빈칸을 그룹 지을때)

그 뒤 matrix에서 벽인 부분만을 찾아 인접 4칸을 순회하며

첫 bfs에서 지정해 둔 그룹인지만 파악해주고

그룹이라면  그 그룹의 수를 더해줌.