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

import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]

N,M = map(int,input().split())

MAP = []
for i in range(N):
  MAP.append(list(map(int,list(input().strip()))))

wall = []
for i in range(N):      #벽 좌표 찾기
  for j in range(M):
    if MAP[i][j] == 1:
      wall.append((i,j))

cntlist = {}
def BFS(y,x,num):
  dq = deque()
  dq.append((y,x))
  cnt = 0
  while dq:
    y,x = dq.popleft()
    if MAP[y][x] != 0:
      continue
    MAP[y][x] = num
    cnt += 1
    for i in range(4):
      y1 = y+dy[i]
      x1 = x+dx[i]
      if N>y1>=0 and M>x1>=0:
        if MAP[y1][x1] == 0:
          dq.append((y1,x1))
  cntlist[num] = cnt

num = 2
for i in range(N):
  for j in range(M):
    if MAP[i][j] == 0:
      BFS(i,j,num)
      num += 1

def checkwall(y,x):
  cnt = 1
  S = set()
  for i in range(4):
    y1 = y+dy[i]
    x1 = x+dx[i]
    if N>y1>=0 and M>x1>=0:
      if MAP[y1][x1] >= 2:
        S.add(MAP[y1][x1])
  for num in S:
    cnt += cntlist[num]
  return cnt

result = [[0]*M for i in range(N)]
for i in range(len(wall)):
  ywall,xwall = wall[i]  
  result[ywall][xwall] = checkwall(ywall,xwall)%10

for i in result:
  print("".join(map(str,i)))

벽 부수고 이동하기 4인데 벽 부수고 이동하기 1번보다 더 빨리 푼 문제

 

왜냐면 보통 벽 부수고 이동하기 1번 문제를 3차원 visited 배열로 많이 푸는데 나는 BFS 문제를 풀때 맵 자체를 변형시키는걸 선호해서 그런 방향으로 알고리즘을 찾았었는데, 이 문제가 그때 푼 알고리즘과 거의 유사하게 풀 수 있었다.

 

알고리즘 방식은 맵을 돌면서 0을 만나면 BFS를 돌려 넓이를 구하고 그 구역을 순서에 따라 번호로 마킹한다. (벽이 1이므로 2부터 시작) 그리고 dictionary에 번호마다 넓이를 저장한 뒤, 각 벽에서 상하좌우 4방향의 땅의 번호를 저장하고, 그 땅들의 넓이를 모두 합쳐준다.

 

알고리즘은 완벽했는데 계속 틀렸습니다가 떠서 뭐가 문제인지 한참을 찾았는데, 알고보니 문제에 "10으로 나눈 나머지를 출력" 이라는 말을 빼먹었었다...

 

 

오늘의 교훈) 문제를 끝까지 읽자