[백준] 2206번: 벽 부수고 이동하기 파이썬

https://www.acmicpc.net/problem/2206

벽 부셔버려

 

어렵다

벽을 한번은 부술수있는데

이걸 어떻게 구현해야할지 도저히 떠오르지 않아서...

힌트글 에서 3차원 배열로 방문여부까지 큐에 저장해야한다는 걸 보고 겨우 풀었다.

 

풀이

import sys
from collections import deque

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

def bfs():
  q = deque()
  q.append((0, 0, 0)) # x, y, 벽 파괴 여부
  dist[0][0][0] = 1
  while q:
    x, y, z = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < m:
        if map[nx][ny] == 1 and z == 0:
          nz = 1
          if dist[nx][ny][nz] == inf:
            dist[nx][ny][nz] = dist[x][y][z] +1
            q.append((nx, ny, nz))
        if map[nx][ny] == 0:
          nz = z
          if dist[nx][ny][nz] == inf:
            dist[nx][ny][nz] = dist[x][y][z]+1
            q.append((nx, ny, nz))

inf = float('inf')
n, m = map(int, sys.stdin.readline().split())
map = [list(map(int, list(sys.stdin.readline().strip()))) for _ in range(n)]
dist = [[[inf for _ in range(2)] for _ in range(m)] for _ in range(n)]
bfs()
min_path = min(dist[n-1][m-1][0], dist[n-1][m-1][1])
if min_path == inf:
  print(-1)
else:
  print(min_path)

 

이동칸을 세는 dist 배열을 2차원이 아닌 3차원으로 만들어서

x, y, z(벽 파괴여부 )

이런 식으로 저장했다.

 

어려워.............

왜 난 이방법을 생각을 못하는거지......