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

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

BFS 탐색을 활용해 최단 거리를 구하려고 했고, 기존에는 다익스트라 방식으로 heapq를 활용한 풀이를 시도했다. 하지만, 벽을 부술 수 있는 조건과 낮과 밤이 바뀌는 특성을 고려했을 때 불필요한 비교 연산과 우선순위 큐의 오버헤드로 인해 시간 초과가 발생했다.
다른 분의 Solution을 참고하면서, BFS를 더 효율적으로 활용할 수 있는 방법을 정리하려고 한다.

from collections import deque
import sys

def solution():
    inp = sys.stdin.readline
    n, m, k = map(int, inp().split())
    
    visited = [[[0 for _ in range(m)] for _ in range(n)] for _ in range(k + 1)]
    grid = [list(map(int, inp().strip())) for _ in range(n)]
    
    hq = deque([(0, 0, 0, 1)])  # (벽 부순 횟수, y, x, 현재까지의 거리)
    visited[0][0][0] = 1  # 시작점 방문 처리

    dt = [(-1, 0), (1, 0), (0, 1), (0, -1)]  # 이동 방향

    while hq:
        cnt, y, x, dist = hq.popleft()

        # 도착 지점에 도달하면 최단 거리 출력 후 종료
        if y == n - 1 and x == m - 1:
            print(dist)
            return

        is_day = dist % 2  # 낮(1)인지 밤(0)인지 판별
        
        for dy, dx in dt:
            ty, tx = y + dy, x + dx
            
            if 0 <= ty < n and 0 <= tx < m:
                # 빈 칸으로 이동하는 경우
                if visited[cnt][ty][tx] == 0 and grid[ty][tx] == 0:
                    visited[cnt][ty][tx] = dist
                    hq.append((cnt, ty, tx, dist + 1))
                
                # 벽을 부술 수 있는 경우
                elif cnt < k and grid[ty][tx] == 1 and visited[cnt + 1][ty][tx] == 0:
                    if is_day:  # 낮이라면 벽 부수고 이동
                        visited[cnt + 1][ty][tx] = dist
                        hq.append((cnt + 1, ty, tx, dist + 1))
                    else:  # 밤이라면 기다렸다가 이동
                        hq.append((cnt, y, x, dist + 1))

    print(-1)  # 도착 불가능한 경우

if __name__ == "__main__":
    solution()

문제 해결 과정 및 최적화 과정

기존 코드에서 시간 초과가 발생한 원인

불필요한 4차원 방문 배열 사용

(y, x, 벽 부순 횟수, 낮/밤 상태)를 저장해 메모리 낭비 발생.
낮/밤을 별도의 차원으로 저장하지 않고, dist의 홀짝을 이용해 구별할 수 있음.

3차원 방문 배열 (visited[k][y][x])로 최적화

우선순위 큐(heapq) 사용의 비효율성

다익스트라 방식으로 heapq를 활용했지만, 모든 이동의 가중치가 동일(1)하므로 BFS가 더 적합.heapq.heappush() 및 heappop() 연산이 불필요하게 많아짐. 즉, 하루 기다렸다가 낮에 벽을 깨는 경우를 바로 처리하기 위해 우선순위 큐를 쓰는 것보다 하루 대기하는 작업을 큐에 추가하더라도 deque를 사용하는 것이 더 효율적이었다는 것.

BFS(deque) 활용하여 최적화

불필요한 최소값 비교 연산

dp 배열을 갱신하기 위해 불필요한 min() 연산이 추가되어 연산량 증가.

대소 비교 대신 visited 배열에 값의 유무로 판단