Baekjoon 14442 벽 부수고 이동하기 2 JAVA

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

문제

해당 문제는 map가 주어졌을 때 1,1에서 시작해서 N, M까지 가는 최단 경로(칸 수)를 구하는 문제다.

조건

map의 값이 0인 곳은 이동할 수 없고, 1인 곳은 이동 가능하다.

시작하는 칸과 끝나는 칸도 포함하여 카운트한다.

이동하는 도중 벽을 부수고 이동하는 것이 좀 더 경로가 짧다면 최대 K개 벽을 부수고 이동 가능하다.

이동은 상, 하, 좌, 우로 한 칸씩 이동 가능하다.

이동이 불가능하면 -1을 출력한다.

풀이

해당 문제는 bfs를 이용하여 해결했다.

큐에 넣을 데이터 형식으로는 좌표값과, 이동 횟수, 벽을 부순 횟수를 담아오도록 했다.

방문 체크를 3차원 배열로 두었는데 벽을 부슨 개수를 하나 추가하여 방문 체크를 하도록 했다.

(+1을 해줘야 벽을 안부 슨 것부터 체크 가능)

bfs를 돌리면서 범위를 벗어나면 다음으로 넘어가며, 범위 안에 들어오면 해당 부분이 벽인지 아닌지를 체크한다.

이후 벽이 아니라면 방문했는지 체크해서 방문을 하고 큐에 넣어준다.

벽인 경우에는 벽을 부술 수 있는지 횟수를 체크하고 방문했는지 체크해서 방문을 하고 큐에 넣어준다.

큐에서 빼낼 때 좌표가 N-1, M-1이라면 도착한 상태이므로 해당 이동 횟수를 출력하여주고 리턴해주며 bfs에서 리턴을 만나지 않았다면 -1을 출력해준다.  

코드

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

public class Main {
	static int N, M, K, dy[] = { -1, 1, 0, 0 }, dx[] = { 0, 0, -1, 1 };
	static char[][] map;
	static boolean[][][] visit;
	static Queue<Node> q = new LinkedList<>();
	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());
		map = new char[N][M];
		visit = new boolean[N][M][K+1];
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}
		visit[0][0][0] = true;
		q.offer(new Node(0, 0, 1, 0));
		bfs();
	}

	private static void bfs() {
		while (!q.isEmpty()) {
			Node n = q.poll();
			if (n.y == N - 1 && n.x == M - 1) { //도착 했으면 현재 카운트를 출력함
				System.out.println(n.cnt);
				return;
			}
			for (int i = 0; i < 4; i++) {
				int ny = n.y + dy[i];
				int nx = n.x + dx[i];
				if (ny < 0 || nx < 0 || ny >= N || nx >= M) //배열 범위 벗어나면 멈춤
					continue; 
				if (map[ny][nx] == '0' ) { // 이동 할 수 있는 곳
					if(!visit[ny][nx][n.wall]) { // 방문 안했으면 방문하고 큐에 넣어줌
						visit[ny][nx][n.wall] = true;
						q.offer(new Node(ny,nx,n.cnt+1,n.wall));
					}
				} else { // 벽인 경우
					 if(n.wall <K && !visit[ny][nx][n.wall+1]) { // 벽을 부술수 있고 방문 안했으면 큐에 넣어줌
						 visit[ny][nx][n.wall+1] = true;
						 q.offer(new Node(ny,nx,n.cnt+1,n.wall+1));
                     }
				}
			}
		}
		System.out.println(-1);
	}

	static class Node {
		int y, x, cnt, wall; // 좌표, 카운트, 벽 부순 횟수
		Node(int y, int x, int cnt, int wall) {
			this.y = y;
			this.x = x;
			this.cnt = cnt;
			this.wall = wall;
		}
	}
}

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

참고

해당 문제는 Baekjoon 2206 벽 부수고 이동하기 문제의 업그레이드 문제다.

Baekjoon 2206 벽 부수고 이동하기 JAVA