벽 부수고 이동하기 2


백준 [14442] 벽 부수고 이동하기 2

문제보기
Alt text

풀이

  • bfs
  • visited[][] : 전체적으로 방문체크
  • visited2[][] : 먼저 방문했던 것이 벽을 몇번만에 뚫고온것인지 확인

소스코드

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

public class Main {
	static int N, M, K, ans;
	static int[][] map;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	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];

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}

		ans = 987654321;
		broken();
		if (ans == 987654321)
			ans = -1;
		System.out.println(ans);
	}

	public static void broken() {
		boolean[][] visited = new boolean[N][M];
		int[][] visited2 = new int[N][M];
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { 0, 0, 1, 0 }); // r,c,length,k
		visited[0][0] = true;

		while (!queue.isEmpty()) {
			int[] q = queue.poll();

			if (q[0] == N - 1 && q[1] == M - 1) {
				ans = Math.min(ans, q[2]);
				return;
			}

			for (int k = 0; k < 4; k++) {
				int x = q[0] + dx[k];
				int y = q[1] + dy[k];

				if (isRange(x, y)) {
					if (!visited[x][y]) {
						if (map[x][y] == 0) {
							visited[x][y] = true;
							visited2[x][y] = q[3];
							queue.add(new int[] { x, y, q[2] + 1, q[3] });
						} else {
							if (q[3] < K) {
								visited[x][y] = true;
								visited2[x][y] = q[3] + 1;
								queue.add(new int[] { x, y, q[2] + 1, q[3] + 1 });
							}
						}
					} else {
						if (map[x][y] == 0) {
							if (visited2[x][y] <= q[3])
								continue;
							visited2[x][y] = q[3];
							queue.add(new int[] { x, y, q[2] + 1, q[3] });
						} else {
							if (q[3] < K) {
								if (visited2[x][y] <= q[3] + 1)
									continue;
								visited2[x][y] = q[3] + 1;
								queue.add(new int[] { x, y, q[2] + 1, q[3] + 1 });
							}
						}
					}
				}
			}
		}
	}

	public static boolean isRange(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < M;
	}
}