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

[문제] 

출처 - https://www.acmicpc.net/problem/14442

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

---

[문제 풀이]

이전에 포스팅한 백준 2206 - 벽 부수고 이동하기 와 풀이가 크게 달라질 게 없다. [ 2206문제 해설 ]

백준 - 2206번을 풀 수 있으면 어렵지 않게 이 문제를 해결할 수 있을 것이다.

 

이번 문제는 이전 문제와 다르게 벽을 K개 부실 수 있는 조건이 추가되었다.

K개를 부실 수 있는 조건을 지켜 코드를 만들면 된다.

 

• BFS 사용
• Queue에 X좌표 Y좌표 거리정보 벽을 부순 상태 정보 추가하여 탐색
• 방문처리는 visit[x][y][현재벽을부순개수] 로 처리
• 벽을 만났을 때 벽을 부신 횟수가 K미만 이어야만 벽을 부실 수 있다.
• N, M 에 도달했을 때 종료 그때의 거리 값을 정답으로 출력 
• 탐색이 끝나도 N, M에 도달하지 못할 경우에는 -1 출력 (0, 0 에서 시작했기 때문에 N-1, M-1 에서 종료)

---

[소스 코드]

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

class Node{
	int x,y,dist,boom;
	Node(int x, int y, int dist, int boom){
		this.x = x;
		this.y = y;
		this.dist = dist;
		this.boom = boom;
	}
}


public class Main {
	static final int dx[] = {0,0,1,-1};
	static final int dy[] = {1,-1,0,0};
	static int map[][];
	static boolean visit[][][];
	static int n,m,k,ans;
	
	public static void main(String[] args) throws IOException {
		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());
		
		map = new int[n][m];
		visit = new boolean[n][m][k+1];
		
		for(int i=0; i<n; i++) {
			String s = br.readLine();
			for(int j=0; j<m; j++) {
				map[i][j] = s.charAt(j) -'0';
			}
		}
		
		ans = -1;
	
		bfs();
	
		System.out.println(ans);
	}
	static void bfs() {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(0,0,1,0));
		visit[0][0][0] = true;
		
		while(!q.isEmpty()) {
			Node p = q.poll();
			int x = p.x;
			int y = p.y;
			
			if(x == n-1 && y == m-1) {
				ans = p.dist;
				return;
			}
			
			for(int i=0; i<4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(0>nx || nx >= n || 0 > ny || ny >= m) continue;
				
				
				if(map[nx][ny] == 0 && !visit[nx][ny][p.boom]) {
					visit[nx][ny][p.boom] = true;
					q.add(new Node(nx,ny,p.dist+1,p.boom));
				}else {
					if(p.boom<k && !visit[nx][ny][p.boom+1]) {
						visit[nx][ny][p.boom+1] = true;
						q.add(new Node(nx,ny,p.dist+1,p.boom+1));
					}			
				}
			}					
		}
	}

}