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

2206번: 벽 부수고 이동하기

최단 거리를 구하는 문제이므로 BFS를 쓰는 게 적합하다.

 

일단 큐에는 x, y좌표 뿐만 아니라

현재까지의 이동 횟수,

이전에 벽을 부쉈는지의 여부

도 저장해주어야 한다.

 

벽을 한 번만 부술 수 있기 때문에

이전에 벽을 부순 적이 있으면

그 루트는 앞으로 벽을 뚫고 지나가지 못 한다.

 

그리고 방문 체크를 해줄 때

벽을 한 번 부순 경우와

벽을 부수지 않은 경우

두 가지로 나누어서 체크해주어야 하기 때문에

3차원 배열 visited를 사용해서

[벽 부쉈는지 유무(0 or 1)][x좌표][y좌표]

로 인덱스를 사용해 주었다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_2206_벽_부수고_이동하기 {
	private static int N, M, res = -1;
	private static int arr[][], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	private static boolean visited[][][];
	private static Queue <int[]> q = new LinkedList<>();
	
	public static void bfs() {
		visited[0][0][0] = true;
		q.offer(new int[] {0, 0, 1, 0}); // x, y, 이동 횟수, 이전에 벽 부쉈으면 1 아니면 0
		while(!q.isEmpty()) {
			for(int i = 0; i < 4; i++) {
				int x = q.peek()[0] + dx[i], y = q.peek()[1] + dy[i], crash = q.peek()[3];
				if(x < 0 || x >= N || y < 0 || y >= M || visited[crash][x][y]) continue;
				if(x == N - 1 && y == M - 1) {
					res = q.peek()[2] + 1; // 탈출 성공
					return;
				}				
				if(arr[x][y] == 1) { // 벽이 가로막고 있을 때
					if(crash == 1) continue; // 이미 이전에 벽을 부쉈으면 넘어감
					crash = 1; // 벽을 부숴버림
				}
				visited[crash][x][y] = true; // 벽 부순 경로와 벽 안 부순 경로가 겹치지 않게
				q.offer(new int[] {x, y, q.peek()[2] + 1, crash});				
			}
			q.poll();
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); M = sc.nextInt();
		arr = new int[N][M]; visited = new boolean[2][N][M];
		for(int i = 0; i < N; i++) {
			String st = sc.next();
			for(int j = 0; j < M; j++) arr[i][j] = st.charAt(j) - '0';
		}
		bfs();
		if(N == 1 && M == 1) System.out.println(1);
		else System.out.println(res);
	}
}