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

백준 16933번

✔️ 문제 풀이

◾ 함수 선언?

• 벽 부수고 이동하기 2와 문제는 거의 동일
• 밤과 낮을 체크해주는 변수를 선언하고, 이를 큐에 저장하여 벽을 부술 때 체크하는 것만 추가해주면 됨
• 그런데 계속해서 시간초과 발생
• 질문 게시판을 보니 bfs를 실행하는 부분을 함수로 선언하여 실행하면 시간초과 발생한다고 한다.
• 별도의 함수 선언 없이 bfs를 구현해줬더니 통과했다... 왜지?

최종 제출 코드

import sys
from collections import deque
input = sys.stdin.readline

N, M, K = 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(K+1)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited[0][0][0] = True

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

while q:

  x, y, cnt, distance, day = q.popleft()

  if x==M-1 and y==N-1:
    result = distance
    break
  
  for i in range(4):

    nx = x + dx[i]
    ny = y + dy[i]

    if nx < 0 or nx >= M or ny < 0 or ny >= N:
      continue
    
    if grid[ny][nx] == 1:
      if cnt < K and day and not visited[cnt+1][ny][nx]:
        visited[cnt+1][ny][nx] = True
        q.append((nx, ny, cnt+1, distance+1, False))
      elif cnt < K and not day and not visited[cnt+1][ny][nx]:
        q.append((x, y, cnt, distance+1, True))
    else:
      if not visited[cnt][ny][nx]:
        visited[cnt][ny][nx] = 1
        q.append((nx, ny, cnt, distance+1, not day))

print(result if result else -1)

✔️ 실행 결과