[백준] 14442 벽 부수고 이동하기 2 (Java)

[14442 벽 부수고 이동하기 2]

난이도: 골드3

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

문제

입력

출력

---

[아이디어]

2206번: 벽 부수고 이동하기

위의 문제의 업그레이드 버전이다. 저 문제를 먼저 풀고 지금 문제를 푸는 것이 좋을 것 같다!

참고로 위의 문제 풀이는 [백준] 2206 벽 부수고 이동하기 (Java) (tistory.com) 여기서 볼 수 있다 ㅎㅎ

 

비슷하게 풀면 되는데, 다른 점은 파괴할 수 있는 횟수가 여러번이라는 점이다. 그래서 Point 클래스에서 현재까지 파괴한 횟수를 저장하는 변수를 만들었다.

static class Point {
    int r, c, k, cnt;

    public Point(int r, int c, int k, int cnt) {
        this.r = r;
        this.c = c;
        this.k = k;
        this.cnt = cnt;
    }
}

 

그리고 해당 위치를 방문했는지 체크해주는 배열에서 파괴한 횟수가 0번부터 K번인지에 따라 다르게 체크해주어야 하기 때문에 3차원 배열로 만들었다.

마지막으로 BFS를 돌면서 벽을 만났을 때와 벽이 아닌 경우를 다르게 체크해주고, 현재까지의 파괴 횟수에 따라 수행해주면 된다!

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, M, K;
	static int [][] map;
	static boolean [][][] visited;
	static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
	
	static class Point {
		int r, c, k, cnt;
		
		public Point(int r, int c, int k, int cnt) {
			this.r = r;
			this.c = c;
			this.k = k;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());

		map = new int [N][M];
		visited = new boolean [N][M][K + 1]; // 0~K번
		for(int r = 0; r < N; r++) {
			String line = br.readLine();
			for(int c = 0; c < M; c++) {
				map[r][c] = line.charAt(c) - '0';
			}
		}
		
		System.out.println(bfs() + "\n");
	}

	private static int bfs() {
		Queue<Point> Q = new LinkedList<>();
		
		Q.offer(new Point(0, 0, 0, 0));
		visited[0][0][0] = true;
		
		while(!Q.isEmpty()) {
			Point now = Q.poll();
			
			if(now.r == N - 1 && now.c == M - 1) {
				return now.cnt + 1; // 목적지에 도착하면 빠져나오기
			}
			
			for(int i = 0; i < 4; i++) {
				int nr = now.r + dr[i];
				int nc = now.c + dc[i];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; // 인덱스 벗어난 경우
				
                		// 벽을 만났는데 아직 파괴할 수 있고, 아직 방문하지 않은 경우
				if(map[nr][nc] == 1 && now.k < K && !visited[nr][nc][now.k + 1]) {
					Q.offer(new Point(nr, nc, now.k + 1, now.cnt + 1));
					visited[nr][nc][now.k + 1] = true;
				}
                		// 벽이 아니고, 아직 방문하지 않은 경우
				if(map[nr][nc] == 0 && !visited[nr][nc][now.k]) {
					Q.offer(new Point(nr, nc, now.k, now.cnt + 1));
					visited[nr][nc][now.k] = true;
				}
			}
		}
        
        return -1; // 목적지에 도착하지 못한 경우이므로 -1 반환
	}

}