import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]
N,M = map(int,input().split())
MAP = []
for i in range(N):
MAP.append(list(map(int,list(input().strip()))))
wall = []
for i in range(N): #벽 좌표 찾기
for j in range(M):
if MAP[i][j] == 1:
wall.append((i,j))
cntlist = {}
def BFS(y,x,num):
dq = deque()
dq.append((y,x))
cnt = 0
while dq:
y,x = dq.popleft()
if MAP[y][x] != 0:
continue
MAP[y][x] = num
cnt += 1
for i in range(4):
y1 = y+dy[i]
x1 = x+dx[i]
if N>y1>=0 and M>x1>=0:
if MAP[y1][x1] == 0:
dq.append((y1,x1))
cntlist[num] = cnt
num = 2
for i in range(N):
for j in range(M):
if MAP[i][j] == 0:
BFS(i,j,num)
num += 1
def checkwall(y,x):
cnt = 1
S = set()
for i in range(4):
y1 = y+dy[i]
x1 = x+dx[i]
if N>y1>=0 and M>x1>=0:
if MAP[y1][x1] >= 2:
S.add(MAP[y1][x1])
for num in S:
cnt += cntlist[num]
return cnt
result = [[0]*M for i in range(N)]
for i in range(len(wall)):
ywall,xwall = wall[i]
result[ywall][xwall] = checkwall(ywall,xwall)%10
for i in result:
print("".join(map(str,i)))
벽 부수고 이동하기 4인데 벽 부수고 이동하기 1번보다 더 빨리 푼 문제
왜냐면 보통 벽 부수고 이동하기 1번 문제를 3차원 visited 배열로 많이 푸는데 나는 BFS 문제를 풀때 맵 자체를 변형시키는걸 선호해서 그런 방향으로 알고리즘을 찾았었는데, 이 문제가 그때 푼 알고리즘과 거의 유사하게 풀 수 있었다.
알고리즘 방식은 맵을 돌면서 0을 만나면 BFS를 돌려 넓이를 구하고 그 구역을 순서에 따라 번호로 마킹한다. (벽이 1이므로 2부터 시작) 그리고 dictionary에 번호마다 넓이를 저장한 뒤, 각 벽에서 상하좌우 4방향의 땅의 번호를 저장하고, 그 땅들의 넓이를 모두 합쳐준다.
알고리즘은 완벽했는데 계속 틀렸습니다가 떠서 뭐가 문제인지 한참을 찾았는데, 알고보니 문제에 "10으로 나눈 나머지를 출력" 이라는 말을 빼먹었었다...
오늘의 교훈) 문제를 끝까지 읽자