백준 16933 | 벽 부수고 이동하기 3 | python 풀이

문제

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

16933번: 벽 부수고 이동하기 3

내 답안

# 16933 벽 부수고 이동하기3
from collections import deque
import sys

n, m, k = map(int, input().split())
visited = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(k + 1)]
graph = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]
d = deque([(0, 0, 0, 1)]) # k, n, m, 현재까지의 거리
visited[0][0][0] = 1

while d:
  ck, cn, cm, dist = d.popleft()  # dist : 밤/낮 정보이자 거리정보
  # 도착
  if cn == n - 1 and cm == m - 1:
    print(dist)
    break

  # 탐색
  day = dist % 2  # dist가 짝수면 밤
  for dn, dm in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
    nn, nm = cn + dn, cm + dm
    if (0 <= nn < n and 0 <= nm < m):
      # 일반 탐색
      if visited[ck][nn][nm] == 0 and graph[nn][nm] == 0:
        visited[ck][nn][nm] = dist
        d.append((ck, nn, nm, dist + 1))

      # 첫 방문인 벽 부수기
      elif (ck < k and graph[nn][nm] == 1 and visited[ck + 1][nn][nm] == 0):
        # 낮이라면
        if day:
          visited[ck + 1][nn][nm] = dist
          d.append((ck + 1, nn, nm, dist + 1))
        # 밤이라면
        else:
          d.append((ck, cn, cm, dist + 1)) # 하루 대기

else:
  print(-1)

해설

벽 부수기 시리즈 문제 중에서 가장 난이도가 있는 문제이지 않았나 싶다.

현재 시점이 낮인지 밤인지 판단하는 과정에서 애를 먹었는데, 이 부분만 잘 해결하니 별다른 고비는 없었던 것 같다.

 

이 문제를 해결하기 위해 큐에 위치정보, 벽을 부순 횟수 뿐만 아니라 현재까지 지나온 거리정보도 함께 저장한다. 

여기서 매 위치마다 지나온 거리값이 짝수면 밤, 홀수면 낮으로 판단한다. 

 

탐색을 위해 방문여부이자 거리정보를 저장할  visited 배열을 준비한다. 

매 탐색에서 다음 위치로 이동할 때를 살펴보자.

 

다음 위치는 두 가지 경우로 나눌 수 있다.

1) 일반적으로 지나갈 수 있는 위치인 경우

2) 벽이라서 부수고 지나가야 하는 경우

 

1)의 경우라면 visited 배열에 현재까지 지나온 거리정보 dist를 저장하고 큐에 dist +1 을 넣어준다.

 

2)의 경우라면 현재가 낮인지, 밤인지에 따라 수행 내용이 달라진다.

낮이라면 벽을 부술 수 있으므로 현 k에서 1을 더해준 위치에 거리 정보 dist를 저장한다. 그리고 큐에 벽을 부순 횟수+1, 위치 정보, dist+1을 넣어주면 된다.

밤이라면 하루를 대기해야 부술 수 있기 때문에 큐에 벽을 부순 횟수, 위치 정보, dist+1를 넣어준다. 

 

피드백

• 현재 지나온 거리 정보를 활용하여 낮/밤을 판단하는 아이디어를 떠올리기 어려웠다.

'PS > 백준 boj' 카테고리의 다른 글

백준 13913 | 숨바꼭질 4 | python 풀이  (0)	2024.04.01
백준 1600 | 말이 되고픈 원숭이 | python 풀이  (0)	2024.03.29
백준 2146 | 다리 만들기 | python 풀이  (0)	2024.03.22
백준 2573 | 빙산 | Python 풀이  (0)	2024.03.21
백준 5430 | AC | Python 풀이  (0)	2024.02.26