[백준] 2178번 : 미로 탐색 - JAVA [자바]

https://www.acmicpc.net/problem/2178

bfs 알고리즘 문제이다.

(0,0) 부터 시작해 (N-1,M-1) 까지 가는 최단 거리를 구해야 한다.

1. 0,0 부터 시작한다.
2. bfs 알고리즘을 사용한다.
3. 인접한 즉, int[] xMove = {0, 0, -1, 1} int[] yMove = {-1, 1, 0, 0} 을 현재 x, y 에 차례대로 더하면서 상하좌우(인접한) 칸을 탐색한다.
4. 갈 수 있는 칸이며 아직 방문하지 않았으면 큐에 add 한다.
5. 이때, 입력받았던 미로 칸의 수정이 발생 한다.
   5.1 현재는 갈 수 있는 칸은 모두 1 로 초기화 되어 있다.
   5.2 현재 0,0 칸에서 만약에 0,1 칸에 갈 수 있다고 한다면
   5.3 0,1 칸의 숫자 1 을 왔던 칸의 숫자에 + 1 한 숫자로 바꾼다.
   5.4 즉, 한 칸 움직였기 때문에 + 1 해주는 것이다.
   5.5 이것을 반복 한다면 미로 배열의 [N-1][M-1] 칸에는 0,0 칸에서의 거리가 입력 될 것이다.

여기서 중요한 점이 나중에 미로의 거리의 값에 다른 경우의 수가 들어갈 수 있다고 생각할 수 있다.
이 경우 먼저 가장 빠른 거리의 수가 입력되고 나중에 그 칸에 더 긴 거리의 수가 입력되는 경우이다.
이것을 방지하기 위해 if (maze[newX][newY] != 0 && !visited[newX][newY]) 이 조건문을 사용한다.
이미 더 가까운 거리의 수의 경로가 방문했기 때문에 더 느린 경우는 방문하지 못한다!!

또한, x, y 좌표 값을 큐에서 관리하기 위해 spot 이라는 새로운 클래스를 만들어서 사용했다.

public class bj2178 {

    public static int M, N, count;
    public static int[][] maze;
    public static boolean[][] visited;
    static int[] xMove = {0, 0, -1, 1};
    static int[] yMove = {-1, 1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);

        visited = new boolean[N][M];
        maze = new int[N][M];
        count = 0;
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            char[] charArray = line.toCharArray();
            for (int j = 0; j < M; j++) {
                maze[i][j] = Integer.parseInt(String.valueOf(charArray[j]));
            }
        }

        bfs(0, 0);

        bw.write(maze[N - 1][M - 1] + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void bfs(int x, int y) {
        Queue<spot> queue = new LinkedList<>();
        queue.add(new spot(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            spot start = queue.poll();
            for (int i = 0; i < 4; i++) {
                int newX = start.x + xMove[i];
                int newY = start.y + yMove[i];

                if (newX >= 0 && newX < N) {
                    if (newY >= 0 && newY < M) {
                        if (maze[newX][newY] != 0 && !visited[newX][newY]) {
                            queue.add(new spot(newX, newY));
                            maze[newX][newY] = maze[start.x][start.y] + 1;
                            visited[newX][newY] = true;
                        }
                    }
                }
            }

        }
    }

    static class spot {
        int x;
        int y;

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