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

       문제 요약        

- 문제

https://www.acmicpc.net/problem/14442

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

 

- 입출력

이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

 

         아이디어        

벽을 K개까지 부수고 이동해도 된다

조건 에서 visited 배열도 확인해야 하고, crushCnt 가 몇개인지 확인해서 

벽을 부술수 있는지 여부가 결정된다 

 

 

         소스코드        

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

class Main {
	static int N,M,K;
	static int[][] box;
	static int[][] way = {{-1,0},{1,0},{0,-1},{0,1}};
	public static void main(String[] args)throws Exception{
		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());
		
		box = new int[N][M];
		for(int n = 0; n < N; n++) {
			String line = br.readLine();
			for(int m = 0; m < M; m++) {
				box[n][m] = line.charAt(m)-'0';
			}
		}
		int shortRoute = bfs(0,0);
		System.out.println(shortRoute);
	}
	static int bfs(int sx, int sy) {
		boolean[][][] visited = new boolean[K+1][N][M];
		Queue<Item> queue = new ArrayDeque<>();	
		visited[0][sx][sy] = true;
		queue.add(new Item(sx,sy,1,0));
		
		while(!queue.isEmpty()) {
			Item now = queue.poll();
			if(now.x == N-1 && now.y == M-1) {
				return now.dist;
			}
			for(int w = 0; w < 4; w++) {
				int nx = now.x + way[w][0];
				int ny = now.y + way[w][1];
				if(nx < 0 || nx >= N || ny < 0 || ny >= M)continue;
				if(!visited[now.crushCnt][nx][ny] && box[nx][ny] == 0) { // 방문한 적이 없고 갈 수 있다면
					visited[now.crushCnt][nx][ny] = true;
					queue.add(new Item(nx, ny, now.dist+1, now.crushCnt));		
				} else {
					if(now.crushCnt < K && !visited[now.crushCnt+1][nx][ny]) {
						visited[now.crushCnt+1][nx][ny] = true;
						queue.add(new Item(nx,ny,now.dist+1, now.crushCnt+1));
					}
				}
				
			}
		}
		return -1;
	}
	static class Item {
		int x, y, dist;
		int crushCnt;
		Item(int x, int y, int dist, int crushCnt) {
			this.x = x;
			this.y = y;
			this.dist = dist;
			this.crushCnt = crushCnt;
		}
		@Override
		public String toString() {
			return ""+x+","+y+" => "+dist+" "+crushCnt;
		}
	}
	
}