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

14442번: 벽 부수고 이동하기 2

14442번: 벽 부수고 이동하기 2

🤔 문제분석

너비우선탐색으로 해결 할 수 있는데 벽을 부순 횟수를 방문배열에 따로 추가하여 해결하였습니다.

벽을 부수고 먼저 이동한 것들이 끝까지 도달하지 못하고 미리 방문배열을 초기화 하였다면 벽을 부수지 않고 온 것이 끝까지 도달하지 못하는 상황이 발생하여 벽을 부순 횟수를 3차원에 추가를하여 벽을 부순횟수도 체크를 해주어야한다.

💻 코드

import sys
from collections import deque
INF = sys.maxsize

input = sys.stdin.readline
N, M, K = map(int, input().split())

graph = []
for _ in range(N):
    graph.append(list(map(int, list(str(input().strip())))))
    
def bfs():
    queue = deque()
    visited = [[[INF]*(K+1) for _ in range(M)] for _ in range(N)]
    queue.append((0, 0, K, 0))
    for i in range(K+1):
        visited[0][0][i] = 0
    
    while queue:
        y, x, wall, cost = queue.popleft()
        #print(y, x, wall, cost)
        for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ny, nx = dy + y, dx + x
            if N > ny >=0 and M > nx >=0:
                new_cost = cost + 1
                # 그냥 이동하는경우
                if graph[ny][nx] == 0:
                    if visited[ny][nx][wall] > new_cost:
                        visited[ny][nx][wall] = new_cost
                        queue.append((ny, nx, wall, new_cost))
                # 벽을 부수고 이동하는경우
                else:
                    if visited[ny][nx][wall-1] > new_cost and wall > 0:
                        visited[ny][nx][wall-1] = new_cost
                        queue.append((ny, nx, wall-1, new_cost))

    return min(visited[N-1][M-1])

ans = bfs()
if ans == INF:
    print(-1)
else:
    print(ans+1)