[🥇2 / 백준 16946 / 파이썬] 벽 부수고 이동하기 4

 

16946번: 벽 부수고 이동하기 4

 

문제

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
예제 입력 2  4 5 11001 00111 01010 10101	예제 출력 2  46003 00732 06040 50403

 

풀이

 

맵을 순환하며 해당 벽을 부쉈을 때 그 영역을 포함하여 0인 영역의 수를 벽이 있는 위치에 표시하여 출력하는 문제이다.

 

맨 처음엔 1인 부분을 순환하며 그 때마다 근처의 0의 영역을 BFS로 탐색하는 알고리즘을 사용했다.

예제는 맞았지만, TLE가 뜨고 말았다.

 

같은 영역에 대해 계속하여 BFS를 진행하기 때문에 반복 작업이 많아서 그런 것 같았다.

따라서 벽 기준이 아니라, 0인 영역을 구한 다음 그 근처의 벽에 영역의 넓이만큼 더해주는 방식으로 바꾸었다.

 

주의할 점은 벽에 영역의 넓이를 더할 때 중복하여 더하지 않도록 해야 하는 것이다.

예제 2의 출력에 6인 부분이 9가 되는 불상사가 생길 수 있다.

 

from collections import deque
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
board = [[-1]*(m+2)]+[[-1]+list(map(int,list(input().rstrip())))+[-1] for _ in range(n)]+[[-1]*(m+2)]
move = [(0,1),(1,0),(0,-1),(-1,0)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if not board[i][j]:
            board[i][j] = -1
            q = deque([(i,j)])
            r = 1; area = set()
            while q:
                x,y = q.popleft()
                for a,b in move:
                    dx = x+a; dy = y+b
                    if not board[dx][dy]:
                        board[dx][dy] = -1
                        q.append((dx,dy))
                        r += 1
                    # 근처의 벽을 중복을 제거하여 좌표를 구한다.
                    elif board[dx][dy] > 0:
                        area.add((dx,dy))
            
            while area:
                x,y = area.pop()
                board[x][y] += r
                
for i in range(1,n+1):
    for j in range(1,m+1):
        if board[i][j] == -1:
            print(0,end="")
        else:
            print(board[i][j]%10,end="")
    print()