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

백준 14442번

✔️ 문제 풀이

◾ 배열 선언

• 문제 로직 자체는 어렵지 않으며 벽 부수고 이동하기 문제와 풀이 유사
• 그러나 계속해서 시간초과 발생
  ⇒ 조건문에 조건을 더 추가해야 하나? 라고 생각해서 조건을 추가했으나 해결되지 않음
• visited를 visited[y][x][벽 부수는 횟수]가 아닌 visited[벽 부수는 횟수][y][x]로 변경했더니 통과!
• N이나 M의 범위보다 K의 범위가 훨씬 작고,
  배열의 경우 list[a][b][c]일 때 a→b→c의 순서보다 c→b→a의 순서로 탐색하는 것이 시간면에서 유리하다
  ⇒ N과 M은 범위가 더 크기 때문에 저차원으로 설정해두는 것이 시간을 줄일 수 있는 방법!

◾ 방문 체크

• (0, 0)으로부터의 거리를 visited에 저장하는 식으로 문제를 풀었으나,
• visited에는 방문 체크만 하고, 출발점으로부터의 거리는 큐에 함께 넣어 전달하는 것이 훨씬 빠르다
  (거리를 업데이트할 때 배열을 탐색하지 않아도 돼서인듯하다)

최종 제출 코드

import sys
from collections import deque

input = sys.stdin.readline
n, m, chance = map(int, input().split())

grid = [list(map(int, input().rstrip())) for _ in range(n)]
visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(chance+1)]
visited[0][0][0] = True

def bfs():

  q = deque()
  q.append((0, 0, 0, 1))

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

  while q:

    x, y, bomb, distance = q.popleft()

    if x==m-1 and y==n-1:
      return distance

    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 grid[ny][nx] == 1:
        if bomb < chance and not visited[bomb + 1][ny][nx]:
          visited[bomb + 1][ny][nx] = True
          q.append((nx, ny, bomb + 1, distance+1))
      else:
        if not visited[bomb][ny][nx]:
          visited[bomb][ny][nx] = True
          q.append((nx, ny, bomb, distance+1))

  return -1

print(bfs())

✔️ 실행 결과