[ 백준 ][ 자바 ][ 2206 ] 벽 부수고 이동하기

음... 이문제는 약간 헷갈리는 문제였다

저번에 풀다가 못풀어서 다시 도전한 문젠대

자꾸 틀려서 다른 분들의 코드를 참고해서 다시 짯다

중요한 점은 벽을 부수냐

 안부수냐 여기서 갈라지는데

벽을 부셨을떄 안부셨을떄를 각각 따져줘야한다

그리고 단 한번만 벽을 부실수 있어야한다는 것이 중요한점이다. 

벽 이었을때 벽이 아니였을때를 구분 짓는데

3차원 배열을 활용해서 벽을 부수었는지 안 부수었는지를 구별해준다.

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

class wallPoint{
	int x;
	int y;
	int wallBreak;
	//int count;
	wallPoint(int y, int x, int wallBreak) {
		this.y = y;
		this.x = x;
		//this.count = count; 
		this.wallBreak = wallBreak;
		
	}
}
public class Main_backjoon_2206_벽부수고이동하기 {
	static int[][] MAP = new int[1001][1001];
	static boolean[][][] visited = new boolean[1001][1001][2];
	static Queue q = new LinkedList();
	static int N;
	static int M;
	static int[] dx  ={1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	public static void main(String[] args) throws IOException {
		//안부셨을떄 0
		//부셨을때 1
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		for(int i = 0; i < N; i++) {
			String[] arr = br.readLine().split("");
			for(int j = 0; j < arr.length; j++) {
				MAP[i][j] = Integer.parseInt(arr[j]);
			}
		}
		//print();
		bfs(0,0);
		
	}
	public static void print() {
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < M; j++) {
				System.out.print(MAP[i][j] + " ");
			}
			System.out.println();
		}
	}
	public static void bfs(int y, int x) {
		visited[y][x][0] = true;
		visited[y][x][1] = true;
		int count = 0;
		boolean canMove = false;
		q.add(new wallPoint(y,x, 0));
		
		loop: while(!q.isEmpty()) {
			count++;
			int qsize = q.size();
			for(int s = 0; s < qsize; s++) {
				wallPoint wp = q.poll();
				//count++;
				if( wp.x == M -1  && wp.y == N - 1) { //도착 
					canMove = true;
					break loop;
				}
				for(int i = 0 ; i < 4; i++) {
					int yy = dy[i] + wp.y;
					int xx = dx[i] + wp.x;
					//System.out.println("count "+ count);
					int wallBreak  = wp.wallBreak;
					if(yy >= 0 && yy < N && xx >= 0 && xx < M) {
						
						if( MAP[yy][xx] == 1 ) { //벽인경우 
							if( wallBreak == 0 && !visited[yy][xx][1] ) {
								visited[yy][xx][1] = true;
								q.add(new wallPoint(yy, xx, 1));
					
							}
						}
						else { // 빈칸인경우 
							if(!visited[yy][xx][wallBreak] ) {
								q.add(new wallPoint(yy, xx, wallBreak));
								visited[yy][xx][wallBreak] = true;
							}
			
						}
					}
				}
			}
		}
	
		System.out.println(canMove ? count : -1 );
		
	}
}