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

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

 

백준 2206번 : 벽 부수고 이동하기 문제와 비슷하다.

 

기존의 벽 부수고 이동하기 문제에서는 벽을 한 번만 부수는 게 가능했는데, 이번 문제에서는 

K가 주어지면, K개만큼 벽을 부수면서 이동이 가능하다.

 

벽 부수고 이동하기에 대한 풀이는 아래 포스팅을 참고

https://lotuslee.tistory.com/142

[백준 2206번] 벽 부수고 이동하기 (java)

 

이번 문제는 K개만큼 벽을 부술 수 있으므로, 특정 위치(nr, nc)에 도착했을 때,

그 위치에 도달하기까지 벽을 몇 번 부수었는지를 확인하기 위해 visited를 3차원 배열로 만든다.

 

boolean[][][] visited = new boolean[N+1][M+1][K+1];

 

특정 위치(nr, nc)에 도착했을 때,

벽을 하나도 부수지 않은 경우 : visited[nr][nc][0]

벽을 1번 부순 경우 : visited[nr][nc][1]

벽을 2번 부순 경우 : visited[nr][nc][2]

...

벽을 k번 부순 경우 : visited[nr][nc][k]

 

 

	import java.io.*;
	import java.util.*;
	public class n14442 {
	static int N, M, K;
	static int[][] board;
	static boolean[][][] visited;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] input = br.readLine().split(" ");
	N = Integer.parseInt(input[0]);
	M = Integer.parseInt(input[1]);
	K = Integer.parseInt(input[2]);
	board = new int[N + 1][M + 1];
	visited = new boolean[N + 1][M + 1][K + 1];
	for (int i = 1; i <= N; i++) {
	String str = br.readLine();
	for (int j = 1; j <= M; j++) {
	board[i][j] = str.charAt(j - 1) - '0';
	}
	}
	bw.write(bfs() + "\n");
	bw.flush();
	}
	public static int bfs() {
	int[] r = { 0, 1, 0, -1 };
	int[] c = { 1, 0, -1, 0 };
	Queue<Pair> q = new LinkedList<>();
	q.offer(new Pair(new Pos(1, 1), 0, 1));
	visited[1][1][0] = true;
	while (!q.isEmpty()) {
	Pair pair = q.poll();
	Pos pos = pair.pos;
	if (pos.r == N && pos.c == M) {
	return pair.cnt;
	}
	for (int i = 0; i < 4; i++) {
	int nr = pos.r + r[i];
	int nc = pos.c + c[i];
	if ((1 <= nr && nr <= N) && (1 <= nc && nc <= M)) {
	if (board[nr][nc] == 0 && !visited[nr][nc][pair.wall]) {
	q.offer(new Pair(new Pos(nr, nc), pair.wall, pair.cnt + 1));
	visited[nr][nc][pair.wall] = true;
	}
	else if (board[nr][nc] == 1 && pair.wall < K && !visited[nr][nc][pair.wall + 1]) {
	q.offer(new Pair(new Pos(nr, nc), pair.wall + 1, pair.cnt + 1));
	visited[nr][nc][pair.wall + 1] = true;
	}
	}
	}
	}
	return -1;
	}
	static class Pair {
	int cnt;
	Pos pos;
	int wall;
	Pair(Pos pos, int wall, int cnt) {
	this.pos = pos;
	this.wall = wall;
	this.cnt = cnt;
	}
	}
	static class Pos {
	int r, c;
	Pos(int r, int c) {
	this.r = r;
	this.c = c;
	}
	}
	}

view raw 14442.java hosted with ❤ by GitHub