🏫 벽 부수고 이동하기 4 (Class 5++)

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

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

def bfs(i, j, group_id):
    q = deque()
    q.append((i, j))
    visited[i][j] = True
    count = 1  # 현재 그룹의 0 개수
    
    while q:
        x, y = q.popleft()
        group_ids[x][y] = group_id  # 그룹 번호 할당
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if visited[nx][ny] or grid[nx][ny] == 1:
                continue
            visited[nx][ny] = True
            q.append((nx, ny))
            count += 1
            
    return count

n, m = map(int, input().split())
grid = [list(map(int, input().strip())) for _ in range(n)]

visited = [[False] * m for _ in range(n)]
group_ids = [[0] * m for _ in range(n)]
group_size = {0: 0}
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
group_id = 1

# 각 0 영역에 대해 BFS 실행
for i in range(n):
    for j in range(m):
        if grid[i][j] == 0 and not visited[i][j]:
            size = bfs(i, j, group_id)
            group_size[group_id] = size
            group_id += 1

# 각 벽(1)에 대해 인접 영역의 0 개수를 합산한 후 결과 계산
for i in range(n):
    for j in range(m):
        if grid[i][j] == 1:
            adj_groups = set()
            for d in range(4):
                ni = i + dx[d]
                nj = j + dy[d]
                if ni < 0 or ni >= n or nj < 0 or nj >= m:
                    continue
                adj_groups.add(group_ids[ni][nj])
            total = 1  # 벽 자체
            for g in adj_groups:
                total += group_size[g]
            grid[i][j] = total % 10

for row in grid:
    print(''.join(map(str, row)))

 

---

✨ 왜 이렇게 풀었을까?

• 해당 문제는 각 벽을 부수고 나서 이동할 수 있는 칸의 개수를 빠르게 구하는 것이 목표였습니다.
• 이젠 이 접근이 너무나도 익숙하지만, 매 벽마다 직접 이동 가능한 칸들을 계속 탐색하는 방식은 반복적인 탐색으로 시간 초과가 발생할 수도 있습니다.
• 그래서 대신에 처음 한 번만 BFS를 통해 0인 영역을 그룹화하고 각 영역의 크기를 계산해 두면, 이후에는 각 벽에 대해서 인접한 영역의 크기들만 단순히 합산시키면 됩니다.
• 중간에 집합 변수(adj_groups)가 추가되어있는데, 하나의 벽이 여러 개의 인접한 0 영역과 접할 때, 같은 그룹에 속하는 영역이 중복해서 계산되는 것을 막기 위해서 선언하였습니다.
• 그리고 최종적으로 벽을 부순 후 이동 가능한 칸의 수를 10으로 나눈 나머지를 출력해야 했기에 문제에서 요구한대로 구현해주었습니다.