/ BOJ

BOJ_2206_벽부수고이동하기_JAVA

문제 : 벽 부수고 이동하기

링크 : BOJ_2206_벽부수고이동하기

접근 방식

BFS를 통한 최단경로 구하는 문제와 유사하다. 이 문제를 풀기 전에 어둠의 경로로 3차원 배열을 사용해야 문제가 풀린다는 정보를 입수했다. 나는 3차원 배열을 사용하지 않고 풀어보려고 했지만 실패했다.

코드 자체는 기존 BFS 문제를 풀 때와 크게 다르지 않다. 바뀌는 점은 노드로 사용할 클래스의 멤버 변수에 벽을 부쉈는지 부수지 않았는지 확인하는 boolean 변수를 하나 추가한 것과, 방문정보를 체크하는 visited boolean 배열에 차원을 하나 늘려 벽을 부순 상태와 부수지 않은 상태의 공간을 분리해주는 부분이다.

풀이 방법

  1. BFS에 사용할 Node 클래스를 하나 만들었다. 멤버변수로는 x,y좌표와 bfs의 깊이를 담을 int변수, 벽 파괴 여부를 저장할 boolean변수가 있다.

  2. 주어진 값을 읽어들여 2차원 배열을 생성해 저장한다. 크기는 N*M크기이다.

  3. 0,0에서 N,M까지 이동하는 문제이므로, bfs를 호출하는데, Node를 하나 생성해주고,(좌표와 깊이는 0으로, 벽은 부수지 않았으니 false로 생성한다.) boolean 3차원 배열을 생성하여 인자값으로 보내준다.

  4. BFS 내부에서는 일반적인 4방탐색 BFS와 동일하게 동작한다.

  5. 4방탐색을 하는 부분에서, 이미 벽을 부순 경우, 벽을 아직 부수지 않은 경우로 나누어서 큐에 offer해준다. 이미 벽을 부순 경우라면, 3차원을 구분하는 index를 1로 바꾸어 공간을 전환시켜준다. 만약 아직 벽을 부수지 않은 상태인데 1을 만난다면 벽을 부순다. 역시 3차원을 구분하는 index를 1로 바꾸어준 뒤 visit 처리한다.

  6. 종료조건을 만족했을 때(좌표가 N,M에 도달했을 때) 종료 노드의 depth를 리턴한다.

  7. 만약 모든 탐색을 완료했는데도 N,M에 도달하지 못했다면 -1를 리턴한다.

  8. 호출부로 돌아와서, 리턴받은 값을 출력한다.

소스 코드


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 BOJ_2206_벽부수고이동하기 {
	static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
	static int N, M;
	static char[][] arr;
	static boolean check;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new char[N][M];

		for (int i = 0; i < N; i++) {
			arr[i] = in.readLine().toCharArray();
		}

		int A1 = bfs(new Node(0, 0, 1, false), new boolean[N][M][2]);

		System.out.println(A1);

	}

	static int bfs(Node node, boolean[][][] visited) {

		Queue<Node> queue = new LinkedList<>();

		queue.offer(node);

		visited[node.x][node.y][0] = true;
		while (!queue.isEmpty()) {

			Node temp = queue.poll();
			if (temp.x == N - 1 && temp.y == M - 1) {
				return temp.depth;
			}

			for (int d = 0; d < 4; d++) {
				int dx = temp.x + dir[d][0];
				int dy = temp.y + dir[d][1];
				if (dx >= 0 && dx < N && dy >= 0 && dy < M) {
					if (arr[dx][dy] == '0') {
						if (!temp.crash && !visited[dx][dy][0]) {
							//
							visited[dx][dy][0] = true;
							queue.offer(new Node(dx, dy, temp.depth + 1, false));
						} else if (temp.crash && !visited[dx][dy][1]) {
							visited[dx][dy][1] = true;
							queue.offer(new Node(dx, dy, temp.depth + 1, true));
						}
					} else if (arr[dx][dy] == '1') {
						if (!temp.crash) {
							queue.offer(new Node(dx, dy, temp.depth + 1, true));
							visited[dx][dy][1] = true;
						}

					}
				}
			}
		}
		return -1;
	}
}

class Node {

	int x;
	int y;
	boolean crash;
	int depth;

	public Node(int x, int y, int depth) {
		super();
		this.x = x;
		this.y = y;
		this.depth = depth;
	}

	public Node(int x, int y, int depth, boolean crash) {
		super();
		this.x = x;
		this.y = y;
		this.depth = depth;
		this.crash = crash;
	}

}