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

1. 문제 링크

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

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 입력을 받고 시작 위치인 0,0에서 부순 벽 개수 0으로 시작한다.

2. BFS로 돌면서 방문 처리를 한다. (해당 위치에서 몇개의 벽을 부쉈는지 확인)

3. size만큼 반복하면서 이동 거리를 더한다.

4. 큐에서 하나씩 뺀다.

    4-1. 뺀 위치가 종료 위치라면 끝낸다.

    4-2. 아니라면 사방탐색을 진행한다.

    4-3. 해당 위치에 벽이 없으면 현재 부순 벽 개수로 온 적이 없다면 방문 처리하고 큥에 넣는다.

    4-4. 해당 위치에 벽이 있으면 벽을 더 부술 수 있는지 확인하고, 부쉈을 때 왔었는지 확인하고 큐에 넣는다.

    4-5. 위의 과정을 반복한다.

5. 종료 위치까지 도착했으면 마지막 위치 칸까지 더해서 출력하고, 아니라면 -1을 출력한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int[] dx = {0,0,-1,1}, dy = {-1,1,0,0};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		int M = Integer.parseInt(split[1]);
		int k = Integer.parseInt(split[2]);
		
		boolean[][] map = new boolean[N][M];
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<M;j++) {
				map[i][j] = str.charAt(j) == '1'? false:true;
			}
		}
		
		//최단경로 => BFS
		boolean[][][] visit = new boolean[N][M][k+1];
		boolean flag = false;
		int result = -1;
		
		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] {0,0,0});
		visit[0][0][0] = true;
		int cnt = 0;
		
		out:
		while(!queue.isEmpty()) {
			int size = queue.size();
			for(int i=0;i<size;i++) {
				int[] now = queue.poll();
				if(now[0] == N-1 && now[1] == M-1) {
					flag = true;
					break out;
				}
				
				for(int d=0;d<4;d++) {
					int X = now[0]+dx[d];
					int Y = now[1]+dy[d];
					int wall = now[2];
					if(X<0 || X>=N || Y<0 || Y>=M) {
						continue;
					}
					if(map[X][Y]) { //벽이 없으면
						if(!visit[X][Y][wall]) {
							visit[X][Y][wall] = true;
							queue.offer(new int[] {X, Y, wall});
						}
					}
					else { //벽이 있으면
						if(wall+1 <= k && !visit[X][Y][wall+1]){
							visit[X][Y][wall+1] = true;
							queue.offer(new int[] {X, Y, wall+1});
						}
					}
				}
			}
			cnt++;
		}
		if(flag) {
			result = cnt+1;
		}
		System.out.println(result);
	}
}