[최단 경로] 백준 2206번 : 벽 부수고 이동하기 / 골드 4

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

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로

www.acmicpc.net

import heapq

x_lim, y_lim = map(int, input().split())

# edge case
if x_lim == 1 and y_lim == 1:
    print(1)
    quit()

table = []
for _ in range(x_lim):
    table.append([int(x) for x in input()])

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

start = [1, 0, 0, 0]  # dist, crush, x, y

visited = [[[False for _ in range(2)] for _ in range(y_lim)] for _ in range(x_lim)]

q = []
heapq.heappush(q, start)
visited[0][0][0] = True

while q:
    dist, crush, x, y = heapq.heappop(q)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < x_lim and 0 <= ny < y_lim and not visited[nx][ny][crush]:
            visited[nx][ny][crush] = True
            if crush + table[nx][ny] <= 1:
                heapq.heappush(q, [dist+1, crush + table[nx][ny], nx, ny])

        if nx == x_lim-1 and ny == y_lim-1:  # finish
            print(dist+1)
            quit()
print(-1)

풀이 포인트:

같은 곳을 방문했더라도,

벽 부술 기회를 사용한 플레이어가 방문한 경우

벽 부술 기회를 사용하지 않은 플레이어가 방문한 경우를 구분해야 한다. (3차원 배열 필요)

그것만 조심하며 다익스트라를 이용해 풀면 된다.