[백준] 2178

 

public class Main {

    static int[] dx = {0, 1, 0, -1};    // 상 하
    static int[] dy = {1, 0, -1, 0};    // 좌 우
    static boolean[][] visited; // 방문한 곳인지 체크할 배열
    static int[][] miro;   // N x M 크기의 미로
    static int n, m;    // N 개의 줄에는 M 개의 정수로 미로가 이루어짐

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        miro = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {   // miro 배열 만들기
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();

            for (int j = 0; j < m; j++) {
                miro[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }

        bfs(0, 0);  // 시작점 : (1, 1) 에서 출발
        System.out.println(miro[n - 1][m - 1]);
    }

    private static void bfs(int i, int j) {
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{i, j});
        visited[i][j] = true;   // 시작점부터 방문 체크

        while (!que.isEmpty()) {
            int now[] = que.poll();

            for (int k = 0; k < 4; k++) {   // 현재 지점에서 상하좌우로 탐색
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];

                // 유효한 좌표인지 확인
                if (x >= 0 && y >= 0 && x < n && y < m) {
                    // 방문하지 않고 0이 아닌 좌표인지 확인
                    if (miro[x][y] != 0 && !visited[x][y]) {
                        visited[x][y] = true;
                        miro[x][y] = miro[now[0]][now[1]] + 1;  // depth 설정
                        que.add(new int[]{x, y});
                    }
                }
            }
        }
    }
}