BOJ 2206 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

문제 분석

- 문제 자체는 bfs로 접근하여 푼다.

cf) 벽을 부수고 방문하는 경우와 벽을 부수지 않고 방문하는 경우를 나눠서 처리해줘야하기때문에 visited배열을 3차원 배열로 만들어서 방문 처리한다.

 

 

문제 풀이

1) 각 좌표상태를 입력 받는다.

2) 해당 좌표상태를 활용하기 위해 Point클래스를 통해 거리(depth)와 go(부시고 이동할 경우 +1)를 사용한다.

3) bfs탐색을 통해 좌표를 탐색한다.

cf) 탐색할 경우 벽인지 아닌지로 구분하여 탐색하고, 벽인 경우엔 우리가 부실 수 있을 때만 큐에 넣고 탐색한다. 벽이 아닌 경우에는 방문 여부만 체크하고 탐색한다. 

 

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, 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, 0));
		visited[x][y][0] = true;

		while (!q.isEmpty()) {
			Point cur = q.poll();
			int r = cur.x;
			int c = cur.y;
			int depth = cur.depth;
			int go = cur.go;

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

			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 (map[nr][nc] == 1) { // 벽인 경우
						if (go == 0) { // 부실 수 있을 경우
							q.add(new Point(nr, nc, depth + 1, go + 1)); // 벽을 부셔줌 (go+1)
							visited[nr][nc][go] = true;
						}
					} else if (map[nr][nc] == 0) { // 벽이 없는 경우
						if (!visited[nr][nc][go]) { // 아직 방문하지 않은 경우
							q.add(new Point(nr, nc, depth + 1, go));
							visited[nr][nc][go] = true;
						}
					}
				}

			}
		}
		return 0;

	}

	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());
		map = new int[N][M];
		visited = new boolean[N][M][2]; // 벽을 뚫은 경우와 안뚫은 경우 따로 체크해줘야하기때문에

		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 == 0 ? -1 : ans);

	}// input()

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

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

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

	}
}