[백준-16946] 벽 부수고 이동하기 4 🧱🔨

❓ Problem

🤔 How

• 기존 이동가능 한 통로(0) 은 항상 0이다
• 반환해야 할 map 형태는 벽을 깬이후 이동할수있는 거리의 최대값 이다. 각 위치에서 최대 이동거리를 기록한다.

최적화

벽을 깬이후 해당 위치에서 상 하 좌 우 를 탐색하며 갈수있는거리를 구하는건 굉장히 비효율적이다. 이를 위해 미리 캐싱해두는 법이 필요하다.

회색은 벽이며 흰색은 이동가능한 통로를 나타냄.

이제 이를 이동 가능한 통로를 다음과 같이 그룹으로 묶어 줄 수 있다.

회색이 아닌 색칠된 통로들 그룹을 표현

위의 그림에서는 연두색이 5칸, 분홍색이 4칸 주황색이 1칸 인 그룹으로 구분 된다. 이를 그룹별로 나누고 그룹의 크기가 얼마나 되는지 표시한 자료구조가 필요하다.

깰벽을 기준으로 상하 좌우 탐색을 하고 (기본값+1 : 깨진벽은 통로가 될수 있으므로) 과 상 하 좌 우를 탐색해서 만날수 있는 통로의 그룹을 더해준다. (그룹이 중복될경우 한번만 더해야함)

❗ Solve

    # 벽 부수고 이동하기 4
import sys
from collections import deque
moves=[(0,1),(0,-1),(1,0),(-1,0)]
input =sys.stdin.readline
PATH='0'
WALL='1'
group_area={}
group_number=1

def draw_board(rows):
    return [input().strip() for _ in range(rows)]

def mark_board():
    global group_number,rows,coloums,group_area

    for y in range(rows):
        for x in range(coloums):
            if board[y][x]==PATH and not marked_group_number[y][x]:
                group_area[group_number]=bfs(y,x)
                group_number+=1

def bfs(y,x):
    global visited,group_number
    q=deque()
    q.append((y,x))

    visited[y][x]=True
    cnt=1

    while q:
        cy,cx=q.popleft()
        marked_group_number[cy][cx]=group_number

        for dy,dx in moves:
            ny,nx=cy+dy,cx+dx

            if 0<=ny<rows and 0<=nx<coloums and not visited[ny][nx] and board[ny][nx]==PATH:
                q.append((ny,nx))
                visited[ny][nx]=True
                cnt+=1
    return cnt


    pass
def calculate_able(y,x): # yx에서 이동가능한 그룹과 그결과
    data=set()
    cnt=1 

    for dy,dx in moves:
        ny,nx=y+dy,x+dx
        if 0<=ny<rows and 0<=nx<coloums and board[ny][nx]==PATH:
            data.add(marked_group_number[ny][nx])

    for value in data:
        cnt+=group_area[value]

    return cnt%10

def solution():

    global visited,group_number,marked_group_number,ans,board,rows,coloums

    rows,coloums=map(int,input().split())

    # init value
    visited=[[False]*coloums for _ in range(rows)]
    marked_group_number=[[0]*coloums for _ in range(rows)]
    ans=[[0]*coloums for _ in range(rows)]

    #draw board
    board= draw_board(rows)

    #mark board    
    mark_board()


    #real solution
    for y in range(rows):
        for x in range(coloums):
            if board[y][x]==WALL: # 벽일때 깨고 갈수잇는경우 구하기
                ans[y][x]=calculate_able(y,x)

    #print
    for line in ans:
        print(''.join(map(str,line)))    

    pass

if __name__=="__main__": # 실행되는 부분
    solution()
    pass