문제 이해

N * M 크기 숫자 배열이 존재하고, 0과 1로만 이루어져 있다.
1은 이동할 수 있는 길이고, 0은 이동할 수 없는 칸이다.

이 때 (1,1) ⇒ (N,M)으로 갈 수 있는 최소 칸수를 구하는 문제이다.

---

문제 풀이

가중치가 없는 그래프에서 A ⇒ B까지의 최소 거리를 구하는 문제이다.

BFS를 통해 해결하면 풀릴 문제이다.

---

코드

import java.io.*;
import java.util.*;

class Sub{
	int x;
	int y;
	int length;
    // x,y : 좌표, length : (1,1)에서 현재 좌표까지 거리
	public Sub(int x, int y, int length) {
		this.x = x;
		this.y = y;
		this.length = length;
	}
}

public class Main {
	static int N,M;
	static boolean[][] arr;
	static boolean[][] visit;

	static Integer dfs() {
		Queue<Sub> go = new LinkedList<>();
		
		go.add(new Sub(0,0,1));
		
		while(!go.isEmpty()){
			
			Sub tmp = go.poll();

			if(tmp.x==N-1 && tmp.y==M-1) return tmp.length;
            // BFS는 (N,M)점을 처음 방문한 순간이 최소 이므로 
            // 이 때의 length가 답이 될 것이다.
			if(visit[tmp.x][tmp.y]) continue;
            // 이미 방문했던 점은 다시 방문할 필요가 없다.
			
			visit[tmp.x][tmp.y] = true;
			
			if(tmp.x+1 < N && arr[tmp.x+1][tmp.y]){
            			go.add(new Sub(tmp.x+1,tmp.y,tmp.length+1));
                        }
			if(tmp.x-1 >= 0 && arr[tmp.x-1][tmp.y]) {
            			go.add(new Sub(tmp.x-1,tmp.y,tmp.length+1));
              		    }
			if(tmp.y+1 < M && arr[tmp.x][tmp.y+1]) {
            			go.add(new Sub(tmp.x,tmp.y+1,tmp.length+1));
                        }
			if(tmp.y-1>=0 && arr[tmp.x][tmp.y-1]){
            			go.add(new Sub(tmp.x,tmp.y-1,tmp.length+1));
                        }
			
		}
		return 0;
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		M = sc.nextInt();
		arr = new boolean[N][M];
		visit = new boolean[N][M];
		
		for(int i =0;i<N;i++) {
			String tmp = sc.next();
			for(int j =0;j<M;j++) {
				if(tmp.charAt(j)=='1') arr[i][j] = true;
			}
		}
		
		System.out.println(dfs());
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과