백준 14442. 벽 부수고 이동하기 2

tose33 2022. 9. 23. 13:16

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

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

www.acmicpc.net

bfs를 이용해서 최단거리를 계산하는데, 벽을 뚫을 기회가 K번 있다.

따라서 큐에 현재 좌표, 깊이, 남은 벽을 뚫을수 있는 기회를 저장한다.

문제의 핵심은 중복 방문을 피하기 위해서 방문을 기록할 3차원 배열 mark[N][M][K] 를 만드는 것이다.

mark[2][2][1]은 (2,2)에 벽을 뚫을 기회가 1회 남았을때 도달할수 있는 최단 거리이다.