풀이
[백준 2206] 벽 부수고 이동하기 [Java]
풀이 (0, 0)에서 (N - 1, M - 1)까지 최대 벽을 1개 부수며 도착할 수 있는 최단거리를 구하면 되는 문제다. 하나의 2차원 배열에 최단거리를 기록하기에는 어느 순간 벽을 부술때와 부수지 않는 경우
kyr-db.tistory.com
위 문제의 확장 버전이다.
벽을 최대 K개 부수며 이동할 수 있다.
이전 로직에서 탐색 중 벽이 아닌 부분을 만났을 때 처리하는 부분을 0 또는 1이 아니라,
지금까지 부순 횟수(smash) + 1로 변경해 처리해주자.
그리고 마찬가지로, 벽을 0 ~ 10개 부순 경우에 대한 이동경로를 기록해야 하니 2개가 아닌, K+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
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 21665] Миша и негатив [Python] (0) | 2023.07.19 |
|---|---|
| [백준 21638] SMS from MCHS [Python] (0) | 2023.07.19 |
| [백준 27172] 수 나누기 게임 [Java] (0) | 2023.07.13 |
| [백준 14938] 서강그라운드 [Java] (0) | 2023.07.12 |
| [백준 1939] 중량제한 [Java] (0) | 2023.07.09 |