16946_벽 부수고 이동하기 4

윤승환·2022년 3월 2일

벽 부수고 이동하기

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

벽을 부수고 이동할 수 있는 곳으로 변경한다.

그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

예제 입력 1

3 3
101
010
101

예제 출력 1

303
050
303

Concept

bfs,,,bfs!!bfs!!bfs!!!!!!!!! (틀렸다...ㅋㅋ)
실행시간 초과..
실행시간 초과 이유 : 모든 원소? 해당하는 벽? '1'인 원소에서 계속 BFS탐색을 시도하니,, 상당히 오래걸리는 작업이 된다.
그렇다면,, BFS를 최소한으로 사용하려면?
관점을 뒤바꾸어 생각하도록한다.
통과되어 있는 벽들이 연결되어 있는 개수를 저장...
연결되어 있는 벽들마다 연결되어 있는 개수가 다르므로, 서로 구별하여 저장을 하여야 하고, 이를 dictionary형태로 저장한다.
이렇게 되면 BFS탐색을 많이 할 필요가 없음..(방문한 정보를 저장하므로 이전에 방문했던 곳을 skip하므로)
FloodFill algorithm 이라고 함.
이 후, '1'이라는 벽에서 자기 주변에 연결되어 있는 벽들의 정보를 모두 더하면 됨.

Code

def bfs(i,j,num):
    cnt = 1
    graph[i][j] = num
    Q = []
    Q.append((i,j))
    while(Q):
        curr = Q.pop()
        for i in range(4):
            new_x, new_y = curr[0]+move[i][0], curr[1]+move[i][1]
            if((0<= new_x <n) and (0<= new_y <m) and visit[new_x][new_y]==False and graph[new_x][new_y]==0):
                visit[new_x][new_y] = True
                graph[new_x][new_y] = num
                Q.append((new_x,new_y))
                cnt += 1
    return cnt
    


def check(row,col, dic):
    what = set()
    for i in range(4):
        new_row, new_col = row+move[i][0], col+move[i][1]
        if((0<= new_row < n) and (0<= new_col<m) and graph[new_row][new_col]!= 1):
            what.add(graph[new_row][new_col])
    cnt = 1
    for i in what:
        cnt += dic[i]
    return cnt


n, m = map(int,input().split())
graph = [[]for _ in range(n)]
for i in range(n):
    graph[i] = list(map(int, input()))

move = ((-1,0),(1,0),(0,-1),(0,1))
dic = {}
visit = [[False for _ in range(m)] for _ in range(n)]
num = 2
for i in range(n):
    for j in range(m):
        if(not visit[i][j] and not graph[i][j]):
            dic[num] = bfs(i,j,num)
            num+=1

answer = [[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if(graph[i][j] == 1):
            answer[i][j] = check(i,j, dic)%10

for i in range(n):
    for j in range(m):
        print(answer[i][j],end = '')
    print()