[C++] 14442 벽 부수고 이동하기 2 | 그래프 탐색, 3차원 방문 체크

백준

코소빵 2023. 9. 29. 17:46

교수님들이 쓰시는 표현을 빌리면,

나에게 너무 challenging하다..

방문 체크 배열을 3차원으로 만들어야 하는 것이 특히 그렇다.

1. 문제 분석

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

미로를 탐색하며 (0, 0)에서 (N-1, M-1)까지의 최단 경로를 찾아야 한다.

이때 부술수 있는 벽의 최대 개수만 지키면 되고 적게 벽을 부수든, 많이 부수든 관계 없다.

따라서 각 위치를 탐색하며 (0, 0)으로부터의 거리를 저장하거나 방문 체크를 할 때에

몇개의 벽을 부수며 왔는지 경우를 나누어 저장해야하는 것이다.

즉, 거리 저장용 배열 dist와 방문 체크용 배열 visited가 미로 2차원 + 부순 벽의 개수 1차원 = 3차원이 되어야한다.