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

📩 출처

문제

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

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

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

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

입력

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

출력

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

👉 생각

• 이 문제는 1일 때마다 bfs나 dfs를 돌려서 체크하는 식으로 하면 시간초과가 발생하는 것 같다.
• 따라서 다르게 생각을 해야하는데, 먼저 주어지는 배열에서 0인 지점을 대상으로 주변이 0인 곳들을 너비 우선 탐색을 한다. 탐색이 가능한 곳의 좌표를 check에 담아두고 check에 있는 좌표들의 값을 check로 바꿔준다.
  • 즉, 같은 묶음의 0인 애들을 구분하기 위해서 값을 변경해주는건데... 일단 귀찮아서 메모리 생각은 안하고 check로 넣어주었다.
  • 이렇게 되면 방문 처리된 0은 너비우선 탐색을 하지 않게 되고, 주어지는 배열에서 같은 묶음의 0끼리는 묶음 내 0의 좌표들이 담긴 리스트가 값으로 들어간다.
• 그렇게 되면 이차원 배열 grid는 1과 같은 묶음의 좌표들이 들어간 리스트로 이루어지게 된다. 그러면 grid에서 1일때 위, 아래, 좌, 우를 탐색해서 리스트의 값이 다른 애들 (즉, 묶음이 다른 애들)만 그 길이를 더해주고 10으로 나눈 나머지를 입력하면 통과할 수 있다!

import sys
from collections import deque

def bfs(x, y):
    q = deque([])
    q.append((x, y))
    visited[x][y] = 1
    check = [(x, y)]
    while q:
        x, y = q.popleft()
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and arr[nx][ny] == '0':
                q.append((nx, ny))
                visited[nx][ny] = 1
                check.append((nx, ny))
    for i, j in check:
        grid[i][j] = check

n, m = map(int, input().split())
arr = [list(sys.stdin.readline().rstrip())for _ in range(n)]
visited = [[0] * m for _ in range(n)]
grid = [[1] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if arr[i][j] == '0' and not visited[i][j]:
            bfs(i,j)

for i in range(n):
    for j in range(m):
        if grid[i][j] == 1:
            lst = []
            for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < n and 0 <= nj < m and type(grid[ni][nj]) != int:
                    if grid[ni][nj] not in lst:
                        lst.append(grid[ni][nj])
            lst = list(map(lambda x : len(x), lst))
            arr[i][j] = str((sum(lst)+1)%10)

for a in arr:
    print(''.join(a))