[BOJ] 2178. 미로 탐색

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

public class Main {
	static int N,M;
	static boolean[][] check;
	static int[][] map;
	static int[] dy = {1, 0 ,-1, 0};
	static int[] dx = {0, 1, 0, -1};
	static int[][] dist;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		map = new int[N][M];
		check = new boolean [N][M];
		dist = new int [N][M];
		for(int i = 0; i < N; i++) {
			String s = sc.next();
			for(int j = 0; j < M; j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}
		
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(0,0));
		check[0][0] = true;
		dist[0][0] = 1;
		while(!q.isEmpty()) {
			Point p = q.poll();			
			for(int i = 0; i < dy.length; i++) {
				int ny = p.y + dy[i];
				int nx = p.x + dx[i];
				if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
				if(!check[ny][nx] && map[ny][nx] == 1) {
					q.add(new Point(ny,nx));
					check[ny][nx] = true;
					dist[ny][nx] = dist[p.y][p.x] + 1; 
				}				
			}
		}
		
		System.out.println(dist[N-1][M-1]);
	}	
	
	static class Point {
		int y,x;
		Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}

import java.util.Scanner;

public class Main {
	static int N, M;
	static int[] dx = {0,1,0,-1}; 
	static int[] dy = {1,0,-1,0};
	static int[][] maze;
	static boolean[][] check;
	static int[][] dp;
	static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		maze = new int [N][M];
		check = new boolean [N][M];
		dp = new int [N][M];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				dp[i][j] = Integer.MAX_VALUE;
			}
		}
		
		for(int i = 0; i < N; i++) {
			String s = sc.next();
			for(int j = 0; j < M; j++) {							
				maze[i][j] = s.charAt(j) - '0'; 				
			}
		}
		
		check[0][0] = true;
		solve(1,0,0);
		System.out.println(answer);
	}
	
	public static void solve(int depth, int y, int x) {
		if(depth >= answer) return;
		if(depth >= dp[y][x]) {
			return;
		} else {
			dp[y][x] = depth;	
		}
		if(y == N-1 && x == M-1) {
			answer = Math.min(answer, depth);
			return;
		}
		
		for(int i = 0; i < dy.length; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];			
			if(isOutOfBound(ny,nx)) continue;
			if(!check[ny][nx] && maze[ny][nx] == 1) {
				check[ny][nx] = true;				
				solve(depth + 1, ny, nx);				
				check[ny][nx] = false;
			}
		}
	}
	
	public static boolean isOutOfBound(int y, int x) {
		if(y < 0 || y >= N || x < 0 || x >= M) return true;
		return false;
	}
}