[백준] 2178 - 미로탐색

전형적인 BFS 문제이다. 

표의 입력이 일반적인 1 0 1 1이 아닌 1011로 들어오는데, String.split("")을 이용해 분리하고 Integer.parstInt로 하는 것보단,

String.charAt() - '0'을 통해 바로 int로 넣어버리는게 훨씬 빠르다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static boolean[][] chk;
    static int[][] arr;

    static int 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());

        arr = new int[N + 1][M + 1];
        chk = new boolean[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            String tmp = br.readLine();
            for (int j = 1; j <= M; j++) {
                arr[i][j] = tmp.charAt(j - 1) - '0';
            }
        }

        BFS(1, 1);

    }

    private static void BFS(int n, int m) {
        int answer = 1;
        arr[n][m] = 0;

        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(n, m));

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point tmp = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = tmp.x + dx[j];
                    int ny = tmp.y + dy[j];

                    if (nx == N && ny == M) {
                        System.out.println(++answer);
                        return;
                    }

                    if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && arr[nx][ny] == 1) {
                        arr[nx][ny] = 0;
                        queue.offer(new Point(nx, ny));
                    }

                }
            }
            answer++;
        }
    }
}