백준 2178 - 미로찾기(feat. java)

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

public class Main {
	
	static int[][] arr; 
	static boolean visited[][];
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	static int N;
	static int M;
	
	static class Point {
		int x;
		int y;
		
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	
	public static void bfs(int x, int y) {
		
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(x,y));
 		
		
		while (!q.isEmpty()) {
			Point p = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nextX = dx[i] + p.x;
				int nextY = dy[i] + p.y;
				
				if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;
				
				if (visited[nextX][nextY] || arr[nextX][nextY] == 0) continue;
				
				q.add(new Point(nextX, nextY));
				
				arr[nextX][nextY] = arr[p.x][p.y] +1;
				
				visited[nextX][nextY] = true;
			}
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in); 
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine();
		
		arr = new int[N][M];
		visited = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			String str = sc.nextLine();
			
			for (int j = 0; j < M; j++) {
				arr[i][j] = str.charAt(j) -'0';
				visited[i][j] = false;
			}
		}
		
		visited[0][0] = true;
		
		bfs(0,0);
		
		System.out.println(arr[N-1][M-1]);
		
	}
}