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

BFS를 공부하고 관련 문제를 풀었다.

그 중 하나를 적어보기로 했다.

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

import java.io.*;
import java.util.*;

// Hammer 클래스는 (x, y) 좌표에 위치한 사람이다.
// 사람은 h 개의 해머를 가지고 있고
// 현재 좌표에 distance 만큼의 거리를 이동하여 도달해있다.
class Hammer {
	int x;
	int y;
	int h;
	int di;
	
	public Hammer(int x, int y, int h, int di) {
		super();
		this.x = x;
		this.y = y;
		this.h = h;
		this.di = di;
	}
}

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		// 2차원 배열에 지도를 담는다.
		int [][] arr = new int[n][m];
		
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = s.charAt(j) - '0';
			}
		}
		
		// 방문 여부를 표시할 배열을 만든다.
		// 방문 여부는 몇 개의 해머를 가지고 방문했냐에 따라 달리 생각한다.
		// 예를 들어 해머를 3개 가지고 있는 사람이 (x, y)에 방문했다면
		// visit[x][y][3] = true 가 된다.
		boolean[][][] visit = new boolean[n][m][k + 1];
		
		// 큐는 Hammer 클래스를 담도록 만들었다.
		Queue<Hammer> queue = new LinkedList<>();
		
		// 시작은 (0, 0)에서 k 개의 해머를 가진 사람.
		queue.add(new Hammer(0, 0, k, 1));
		
		// 델타 배열
		int [] di = {1, -1, 0, 0};
		int [] dj = {0, 0, 1, -1};
		
		// 만약 탈출했다면 즉시 종료하는 escape.
		boolean escape = false;
		
		// 가능한 모든 경로를 전부 탐색. (더 이상 갈 수 있는 좌표가 없는 경우이다.)
		while (!queue.isEmpty()) {
			
			// 큐에서 다음 사람(해머)을 선택한다.
			Hammer hammer = queue.poll();
			
			// 탈출 (Escape)
			if (hammer.x == n - 1 && hammer.y == m - 1) {
				
				// 탈출 시 움직인 거리를 출력한다.
				// BFS 이므로 도달하는 즉시 정답이 된다. (동일한 거리를 다같이 탐색하므로)
				System.out.println(hammer.di);
				
				// 탈출 성공.
				escape = true;
				break;
			}
			
			// hammer 의 좌표를 기준으로 사방탐색한다.
			for (int d = 0; d < 4; d++) {
				int ni = hammer.x + di[d];
				int nj = hammer.y + dj[d];
				
				// 배열의 인덱스를 넘어가지 않는다면.
				if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
					
					// 만약 벽을 만났다면.
					if (arr[ni][nj] == 1) {
						
						// 만약 사람이 해머를 가지고 있다면 부수고 통과할 수 있다.
						// 즉 해머를 하나 소비한다.
						// 부순다고 해서 실제 지도의 1을 없애는 것은 아니다.
						if (hammer.h != 0) {
							
							// 만약 나와 동일한 해머의 개수를 가진 사람이 방문한 적이 없다면.
							if (!visit[ni][nj][hammer.h]) {
								
								// 다음 칸으로 넘어가고, 해머의 개수는 하나 줄어든다.
								// 거리는 하나 늘어난다.
								queue.add(new Hammer(ni, nj, hammer.h - 1, hammer.di + 1));
								
								// 방문 표시
								visit[ni][nj][hammer.h] = true;
							}
						}
						
						// 만약 벽이 아니라면
					} else {
						
						// 나와 동일한 개수의 해머를 가진 사람이 방문한 적이 없다면
						if (!visit[ni][nj][hammer.h]) {
							
							// 벽이 아니므로 해머를 소모하지 않고 움직일 수 있다.
							queue.add(new Hammer(ni, nj, hammer.h, hammer.di + 1));
							visit[ni][nj][hammer.h]= true; 
						}
					}
					
				}
			}
		}
		
		// 만약 escape == false 라면 탈출을 못한 것.
		if (!escape) System.out.println(-1);
	}
}