[백준 14442번] 벽 부수고 이동하기 2 (java)
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
백준 2206번 : 벽 부수고 이동하기 문제와 비슷하다.
기존의 벽 부수고 이동하기 문제에서는 벽을 한 번만 부수는 게 가능했는데, 이번 문제에서는
K가 주어지면, K개만큼 벽을 부수면서 이동이 가능하다.
벽 부수고 이동하기에 대한 풀이는 아래 포스팅을 참고
https://lotuslee.tistory.com/142
[백준 2206번] 벽 부수고 이동하기 (java)
2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하
lotuslee.tistory.com
이번 문제는 K개만큼 벽을 부술 수 있으므로, 특정 위치(nr, nc)에 도착했을 때,
그 위치에 도달하기까지 벽을 몇 번 부수었는지를 확인하기 위해 visited를 3차원 배열로 만든다.
boolean[][][] visited = new boolean[N+1][M+1][K+1];
특정 위치(nr, nc)에 도착했을 때,
벽을 하나도 부수지 않은 경우 : visited[nr][nc][0]
벽을 1번 부순 경우 : visited[nr][nc][1]
벽을 2번 부순 경우 : visited[nr][nc][2]
...
벽을 k번 부순 경우 : visited[nr][nc][k]