import java.util.*;
import java.io.*;
public class Main{
static class Miro {
int x;
int y;
int moved;
public Miro(int x, int y, int moved) {
this.x = x;
this.y = y;
this.moved = moved;
}
}
static int[][] graph;
static int m, n;
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
graph = new int[m+1][n+1];
for (int i = 1; i<m+1; i++) {
String input = bf.readLine();
for (int j = 0; j<n; j++) {
graph[i][j+1] = input.charAt(j)-'0';
}
}
System.out.println(bfs());
}
static int bfs() {
Queue<Miro> queue = new LinkedList<>();
int moved = 0;
queue.add(new Miro(1, 1, 1));
while (!queue.isEmpty()) {
Miro miro = queue.poll();
moved = miro.moved;
for (int i = 0; i<4; i++) {
int nx = miro.x + dx[i];
int ny = miro.y + dy[i];
if (nx > 0 && ny > 0 && nx <= m && ny <= n) {
if (graph[nx][ny] == 1) {
graph[nx][ny] = 0;
queue.add(new Miro(nx, ny, moved+1));
if (nx == m && ny == n) {
return moved+1;
}
}
}
}
}
return moved;
}
}
0과 1로 입력된 2차원 배열이 있다. 1,1부터 m,n까지 1로 이어진 최단 거리를 구하는 문제다.
miro 클래스를 자료형으로 하는 큐를 선언한다.
1, 1을 큐에 넣어주고 bfs탐색을 시작한다. 만약 가로 세로 위 아래에 1이 나오면 0으로 만들어주고 moved를 +1 해서 큐에 저장한다.
이 과정을 반복해서 m, n에 도달하면 moved를 리턴하게 해주었다.
if (nx == m && ny == n) {
return moved+1;
}
처음에 이 조건을 넣어주지 않아서 최단 거리를 계산하지 않고 최장거리를 계산해서 출력해줬다.