[백준] 14442 : 벽 부수고 이동하기2 - Python

문제

nxm 보드. 0은 이동 가능,1은 이동 불가능 벽
(1,1) -> (n,m) 이동하는데 최단경로로 이동 --> 여기서 다익스트라라고 판단
이동 중 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 k개까지 부수고 이동

3차원 배열을 만들어야 하는 이유.

결론적으로 벽을 1~k번 부술 때 현재의 결과가 미래에 영향을 끼치기 떄문에

현재 3번 벽을 부순 경로와 현재 2번 벽을 부순 경로의 최단거리를 비교할 수 없다.

2번 부순게 더 많다고 해서 3번 부순 경로의 길이를 저장해버리면

뒷 경우에 영향을 받아버림.

3번 부쉈을 때가 2번 부쉈을 제때보다 현재 더 최단거리라고 하더라도

3번 부쉈을 때가 도착점에 도달하지 못할 수도 있기 때문에 그때는 그 당시의 경우를 되돌릴 수 없음

그래서 → 이 문제는 3차원 배열로 해결 가능

이유는 벽이 모두 동일 → 각 벽이 모두 동일하다면 해당 각 벽을 부순 횟수를 변수로 조정해서 값을 대입하면 되기 때문.

근데 달이 차오른다처럼 변수가 다르다면 여러개의 체크 변수가 필요한데

이렇게 되면 차원이 너무 커짐.

→ 비트마스킹 사용

앞으로 3차원으로 판단해야 하는 경우 3번째 칸을 체크로 해서 구하자.

그리고 최종 결과물은 dis에 저장된 값들 중 반복문 돌리면서 최종 값을 구해야 한다.(찐 최종 최단거리)

내 코드

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

# nxm 보드, 0은 이동 가능, 1은 벽
# (1,1) -> (n,m) 최단 경로로 이동 : 다익스트라
# 벽을 k개까지 부수고 이동 가능. -> 조건 추가

n,m,k = map(int, input().split()) # 보드 크기, 벽 최대 k번 부수기 가능
g = [list(map(int, input())) for _ in range(n)]

startX, startY = 0,0
endX,endY = n-1,m-1
INF = int(1e9)
dis = [[[INF] * (k+1) for _ in range(m)] for _ in range(n)] # 각각 배열로 닫아주면서 진행해야 3차원
# k번까지 확인해야 하므로 k+1
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def isInner(x,y):
    if 0<=x<n and 0<=y<m:
        return True
    return False
def BFS(startX,startY): # 다익스트라
    global res
    dq = deque()
    dq.append((startX,startY,1,0)) # 시작점, 경로 길이, 벽 부순 횟수 함께 저장

    while dq:
        x,y,t,cnt = dq.popleft() # 현재 좌표, 현재 경로의 길이
        if (x,y) == (endX,endY): # 도착점 도달
            res = min(res, t)
            continue # 도착점에서는 할 필요 없음 !
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not isInner(nx,ny): # 만약 좌표 내부 아니라면 안돼
                continue
            if g[nx][ny] == 0: # 그냥 이동 가능
                if t + 1 < dis[nx][ny][cnt]: # 최단거리 갱신 가능하다면
                    dis[nx][ny][cnt] = t + 1 # 갱신 후
                    dq.append((nx,ny,t+1,cnt)) # 해당 좌표에서 다시 확인
            else: # 이동이 불가능한 경우. 벽 부수고 갈 수 있는지 확인
                if cnt < k:
                    if t + 1 < dis[nx][ny][cnt+1]: # 벽 부수고 최단거리 갱신 가능
                        dis[nx][ny][cnt+1] = t + 1
                        dq.append((nx,ny,t + 1, cnt + 1))

res = INF
BFS(startX,startY)
if res == INF:
    print(-1)
else:
    print(res)

코멘트

다익스트라로 구현하기 때문에, 따로 방문처리할 필요없이 갱신이 된다면 큐에 넣어주는 식으로 구현.