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

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

만약 시간초과를 생각하지 않고 그냥 풀면 1인 지점마다 0으로 바꾼 뒤, bfs를 모두 돌려주면 된다.
이렇게 한다면 만약 최악의 경우에 1000*1000에 모두 1인지점을 놓고 1000000번 bfs를 돌려야 하는데, 시간초과가 날 것이 자명했다. (애초에 그냥 bfs만 하게 두고 정답을 바라면 이정도 난이도가 아니였겠지 아니지,,)

그래서 중복을 어떻게 줄여볼까를 곰곰히 생각하다가,
1이 있는 위치에서 0의 개수를 bfs로 찾는다는 것은 상하좌우bfs의 0의개수가 몇개인지 판별하는 것인데, 문제점이 그 상하좌우로 있는 0이 서로 연결되어 있다면 같은 bfs이기 때문에 이 중복을 제거해주어야 한다는 것이다.

그렇기 때문에 기존 배열에 0을 bfs를 다 돌려서, 같은 그룹끼리 나누어 놓았고, 그 그룹에 0이 몇개 있는지를 기록해 놓았다.
이렇게 만들면, 1이 있는 지점에서 상하좌우에 0이 있다면 그 bfs의 값을 더하고 만약 같은 그룹이 다른 방향에도 있다면 그 방향은 skip하는 방식으로 문제를 풀었다.

from collections import deque
n,m = map(int,input().split())
arr = []
walls = []
for i in range(n):
    row = list(map(int,input()))
    for j in range(len(row)):
        if row[j] == '1':
            walls.append((i,j))
    arr.append(row)

visited = [[0]*m for i in range(n)]
dp = [[0]*m for i in range(n)]
ans = [[0]*m for i in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
cnt = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0 and not visited[i][j]:
            cnt += 1
            queue = deque([])
            queue.append((i,j))
            block = [(i,j)]
            while queue:
                x,y = queue.popleft()
                visited[x][y] = cnt
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and arr[nx][ny] == 0:
                        visited[nx][ny] = cnt
                        block.append((nx,ny))
                        queue.append((nx,ny))
            length = len(block)
            for bl in block:
                bx,by = bl
                dp[bx][by] = length
for i in range(n):
    for j in range(m):
        appended = []
        if arr[i][j] == 0:
            continue
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] not in appended:
                appended.append(visited[nx][ny])
                ans[i][j] += dp[nx][ny]
        ans[i][j] += 1
        ans[i][j] %= 10
for row in ans:
    print(''.join(list(map(str,row))))