백준_2179

package code_test;

import java.util.*;

public class Main {
    // 방향 이동 (상, 하, 좌, 우)
    // 2차원 배열 0,0 부터 시작 
	// x 가 작아지고 y는 변동이 없어야 위로 감
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    public static int bfs(int[][] maze, int n, int m) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0}); // 시작점 (0,0)에서 BFS 시작
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            // 목표 지점에 도달하면 최소 칸 수를 반환
            if (x == n - 1 && y == m - 1) {
                return maze[x][y];
            }

            // 인접한 네 방향 탐색
            for (int i = 0; i < 4; i++) {
            	// 현재 x y 에 상,하,좌,우 로 움직이는 좌표 설정
                int nextX = x + dx[i];
                int nextY = y + dy[i];

                // 배열 인덱스가 마이너스가 아니고, 지정한 좌표 내 이거나, 통과 가능한 미로 이거나, 아직 방문하지 않은 칸이면
                if (nextX >= 0 && nextY >= 0 
                		&& nextX < n && nextY < m 
                		&& maze[nextX][nextY] == 1 
                		&& !visited[nextX][nextY]) {
                	
                	// 큐에 상,하,좌,우 로 움직이는 좌표를 넣고
                    queue.add(new int[]{nextX, nextY});
                    // 해당 좌표를 방문처리 후
                    visited[nextX][nextY] = true;
                    // 재활용 한 배열에 이동거리 적산
                    maze[nextX][nextY] = maze[x][y] + 1; // 이동 거리를 1씩 늘려서 기록
                    
                }
            }
        }

        return -1; // 도달할 수 없는 경우는 입력에 없으므로 여기에 도달하지 않음
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] maze = new int[n][m];

        for (int i = 0; i < n; i++) {
            String line = scanner.next();
            for (int j = 0; j < m; j++) {
                maze[i][j] = line.charAt(j) - '0';
            }
        }

        // BFS를 통해 최소 칸 수를 구함
        int result = bfs(maze, n, m);
        System.out.println(result);
    }
}