[백준][Python]16946번(벽 부수고 이동하기 4)

백준 16946번

✔️ 문제 풀이

◾ 빈공간을 그룹으로 묶어 계산에 활용

• 모든 벽에 대해서 매번 인접한 빈공간을 계산하면 시간초과 발생
• 하나로 묶여있는 빈공간은 각각 번호를 부여해주고, 각 번호에 해당하는 공간의 넓이를 계산한다.
  ⇒ 이 과정을 한 번 수행해서 값을 저장해놓으면, 벽에 인접한 빈공간의 그룹을 검사하고 그 값만 더해서 result 배열을 업데이트 해주면 됨으로 실행 시간이 훨씬 줄어든다

최종 제출 코드

from collections import deque

n, m = map(int, input().split())

matrix = []
# 벽 좌표 입력
walls = []
# 빈공간 좌표 입력
empty = []
# 이어져있는 빈공간을 하나의 그룹으로 묶을 때 쓸 리스트
empty_key = []
visited = [[0] * m for _ in range(n)]
result = [[0] * m for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 전체 배열을 입력받으면서 벽과 빈공간의 좌표 입력 받기
for i in range(n):
  row = input()
  for j in range(m):
    if row[j] == '1':
      walls.append((j, i))
    else:
      empty.append((j, i))
  matrix.append(row)


# 빈공간 계산
def calculate_empty(values):

  xv, yv = values
  # 그룹 번호
  key = len(empty_key) + 1
  visited[yv][xv] = key
  queue = deque()
  queue.append((xv, yv))
  count = 1

  # 이번 순서에서 팝된 원소와 인접한 빈공간은 모두 이 원소와 동일한 그룹 번호를 갖는다
  while queue:

    x, y = queue.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or ny < 0 or nx >= m or ny >= n:
        continue

      if visited[ny][nx] == 0 and matrix[ny][nx] == '0':
        queue.append((nx, ny))
        visited[ny][nx] = key
        # 결과값을 계산할 때 쓰일 그룹 별 원소의 개수 저장
        count += 1
  
  count %= 10
  empty_key.append(count)

# 벽에 대해서 사방의 빈공간을 인식하고, 그룹별 원소의 개수를 더하여 result 배열을 업데이트한다
def calculate_walls(values):

  x, y = values
  keys = []
  
  sum_value = 1
  
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
  
    if nx < 0 or ny < 0 or nx >= m or ny >= n:
      continue
    if visited[ny][nx] and visited[ny][nx] not in keys:
      keys.append(visited[ny][nx])
      sum_value += empty_key[visited[ny][nx] - 1]%10
  
  result[y][x] = sum_value%10

# 아직 방문하지 않은 빈공간에 대해 calculate_empty 를 실행한다
for x, y in empty:
  if not visited[y][x]:
    calculate_empty((x, y))

# 벽에 대해 calculate_walls 를 실행한다
for wall in walls:
  calculate_walls(wall)

# 결과를 출력한다
for i in range(n):
  for j in range(m):
    print(result[i][j], end='')
  print()

✔️ 실행 결과