BOJ 1442 벽 부수고 이동하기 2

www.acmicpc.net/problem/14442

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

 

 

문제 분석

- bfs의 심화문제이다. 

- visited배열을 3차원처리해준다. 벽을 부수는 변수 K를 인덱스로 하여, 변수 K가 변할 때 마다 visited배열을 다르게 체크해줘야 한다.

 

 

문제 풀이

1) 각각의 입력값을 받는다.

2) bfs탐색을 한다.

3) bfs탐색시 벽을 없앨 수 있는 조건이 된다면 벽을 부시고(cnt-1), 벽이 없다면 그냥 이동처리하여 탐색한다.

 

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

public class Main {
	private static int N, M, K, ans;
	private static int[][] map;
	private static boolean[][][] visited;
	private static int[] dr = { -1, 1, 0, 0 }; // 상하좌우
	private static int[] dc = { 0, 0, -1, 1 };

	private static int bfs(int x, int y) {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x, y, 1, K));
		visited[x][y][K] = true;

		while (!q.isEmpty()) {
			Point cur = q.poll();
			int r = cur.x;
			int c = cur.y;
			int depth = cur.depth; // 이동 거리
			int cnt = cur.cnt; 

			if ((r == N - 1) && (c == M - 1)) {
				return depth;
			}

			// 4방 탐색
			for (int d = 0; d < 4; d++) {
				int nr = r + dr[d];
				int nc = c + dc[d];

				if (nr >= 0 && nr < N && nc >= 0 && nc < M) {// 범위 내에 있을 때

					if (!visited[nr][nc][cnt] && map[nr][nc] == 0) { // 그냥 이동하기
						q.add(new Point(nr, nc, depth + 1, cnt));
						visited[nr][nc][cnt] = true;
					}
					// 벽을 부수기 가능할 때
					else if (cnt > 0 && !visited[nr][nc][cnt - 1] && map[nr][nc] == 1) { // 벽 부수고 이동하기
						q.add(new Point(nr, nc, depth + 1, cnt - 1));
						visited[nr][nc][cnt - 1] = true;

					}
				}
			} // 4방탐색

		} // while
		return -1;

	}

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		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];
		visited = 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 = bfs(0, 0);
		System.out.println(ans);

	}// input()

	public static void main(String[] args) throws IOException {
		input();
	}

	static class Point {
		int x;
		int y;
		int depth;
		int cnt;

		Point(int x, int y, int depth, int cnt) {
			this.x = x;
			this.y = y;
			this.depth = depth;
			this.cnt = cnt;
		}

	}
}