[백준][자바][14442]벽부수고 이동하기 2

1과 똑같은 문제 

 

1과 다른점은 1은

벽을 부수고 안부수고 상태값이 2개인데

이번에는 k번까지 부술 수 있다는 것이다

 

k가 1인경우는 한번 만 부신경우

k가 2인경우는 2번 부신경우 이런식으로 가정을 하면 문제가 쉬워진다

 

 

package back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Wall2{
	int x;
	int y;
	int wallBreak;
	Wall2(int y, int x, int wallBreak) {
		this.y = y;
		this.x = x;
		this.wallBreak = wallBreak;
		
	}
}
public class Main_backjoon_14442_벽부수고이동하기2 {
	static int[][] MAP = new int[1001][1001];
	static boolean[][][] VISITED = new boolean[1001][1001][11];
	static Queue q = new LinkedList();
	static int N;
	static int M;
	static int K;
	static int[] dx  ={1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	public static void main(String[] args) throws IOException {
		//안부셨을떄 0
		//부셨을때 1
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		for(int i = 0; i < N; i++) {
			String[] arr = br.readLine().split("");
			for(int j = 0; j < arr.length; j++) {
				MAP[i][j] = Integer.parseInt(arr[j]);
			}
		}
		//print();
		q.add(new Wall2(0,0,0));
		VISITED[0][0][0] = true;
		bfs(0,0);
	}
	public static void bfs(int y, int x) {

		int distance = 1 ;
		while(!q.isEmpty()) {
			int qsize = q.size();
			for(int s = 0 ;s < qsize; s++ ) {
				Wall2 wp = q.poll();
				if(wp.y == N -1  && wp.x == M -1 ) {
					System.out.println(distance);
					return;
				}
				for(int d = 0; d < 4; d++ ) {
					int yy = dy[d] + wp.y;
					int xx = dx[d] + wp.x;
					int wallBreak = wp.wallBreak;
					if(!isRange(yy,xx)) {
						continue;
					}
					if(VISITED[yy][xx][wallBreak]) {
						continue;
					}
				
					if( MAP[yy][xx] == 0 ) {
						q.add(new Wall2(yy,xx,wallBreak));
						VISITED[yy][xx][wallBreak] = true;	
					}
					//벽일경우 
					else if( MAP[yy][xx] == 1 ) {		
						if( wallBreak != K ) { // 벽을 아직 안부쉈다면 
							wallBreak += 1; 
							q.add(new Wall2(yy,xx,wallBreak));
							VISITED[yy][xx][wallBreak] = true;	
						}else {
							continue;
						}
					}
					
				}
			}
			distance +=1 ;
		}
		System.out.println("-1");
		
	}
	public static boolean isRange(int yy, int xx) {
		if( yy >= 0 && yy < N && xx >= 0 && xx < M) {
			return true;
		}else {
			return false;
		}
	}
}