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

🔗 문제

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

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

 

🧩 풀이 및 코드

문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS)

 

풀이

참고 - https://wngml56.tistory.com/79

[BOJ] 2206. 벽 부수고 이동하기 - JAVA

핵심 : 일반(?) BFS 는 어떤 지점 x 에 먼저 도착하면 최단 경로로 해답이 된다. 하지만 이 문제에선 벽을 깨고 x 에 먼저 도착한다고 하더라도 목표지점에 도착하지 못하면 답이 아니다. 벽을 깨지 않고 더 늦게 x 지점에 도착하더라도 목표 지점에 도착한다면 그게 정답이다. 

• 방문 배열을 3차원으로 만든다. (visited[N][M][K])
• 벽을 깨지 않은 경우는 [N][M][0] 에 방문 체크를, 1번 깬 경우는 [N][M][1] 에 방문 체크를, 2번 깬 경우는 [N][M][2] 에 방문 체크를, ... 이런 식으로 K 번 벽을 깰 수 있으면 k 번 깬 경우는 [N][M][k] 에 방문체크를 한다. 
  이유는 위에서 말했듯이, 벽을 깬 경우가 깨지 않은 경우보다 더 빨리 올 순 있어도 답이 아닐 수 있다. 따라서 벽을 꺤 경우를 방문체크하면서 온다면 벽을 깨지 않은 경우엔 이미 방문 처리 되어 있는 곳을 재방문 할 수 없으므로 막히게 된다. 따로 체크해야 한다.
• 최종 목적지에 도착한 경로 중 가장 짧은 값을 출력한다.

느낀 점

이 유형의 문제를 풀기 힘들어했는데 이해하니 재미있다.

 

전체 코드

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

public class Main_bj_14442_벽부수고이동하기2 {
	
	static int N, M, K;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_14442.txt"));
		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());
		
		int[][][] map = new int[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][0] = s.charAt(j)-'0';
				
				if(map[i][j][0] == 1) {
					
					for(int k=0; k<=K; k++) {
						map[i][j][k] = -1;
					}
				}
			}
		}
		
		System.out.println(BFS(map));
		br.close();
	}
	
	static class Loc {
		int x;
		int y;
		int wall;
		
		Loc(int x, int y, int wall) {
			this.x = x; 
			this.y = y;
			this.wall = wall;
		}
	}
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	static int BFS(int[][][] map) {
		map[0][0][0] = 1;
		Queue<Loc> que = new ArrayDeque<>();
		que.add(new Loc(0, 0, 0));				// 현재 정점 x, y, 벽을 꺤 횟수
		
		int res = Integer.MAX_VALUE;
		while(!que.isEmpty()) {
			Loc now = que.poll();
			
			if(now.x == N-1 && now.y == M-1) {
				res = Math.min(res, map[now.x][now.y][now.wall]);
			}
			
			for(int d=0; d<4; d++) {
				int nx = now.x + dx[d];
				int ny = now.y + dy[d];
				
				if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
				if(map[nx][ny][now.wall] == 0) {
					map[nx][ny][now.wall] = map[now.x][now.y][now.wall] + 1;
					que.add(new Loc(nx, ny, now.wall));
				}
				if(now.wall+1 <= K && map[nx][ny][now.wall+1] == -1) {
					map[nx][ny][now.wall+1] = map[now.x][now.y][now.wall] + 1;
					que.add(new Loc(nx, ny, now.wall+1));
				}
			}
		}
		
		if(res >= Integer.MAX_VALUE) return -1;
		else return res;
		
	}

}