2178번 문제 미로 탐색 자바(JAVA) 풀이

문제

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

2178번: 미로 탐색

풀이 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

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

    public static void main(String[] args) {
        //input start
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            char[] charArray = sc.next().toCharArray();
            for (int j = 0; j < charArray.length; j++) {
                map[i][j] = Character.getNumericValue(charArray[j]);
            }
        }
        //input end

        //미로의 최단거리를 구해야 하므로
        //BFS를 하면서 좌표가 (N-1, M-1)이 되면 level(depth)를 출력한다.
        int answer = BFS(N, M, map);
        System.out.println(answer);
    }

    private static int BFS(int N, int M, int[][] map) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(0, 0));
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point curPoint = queue.poll();
                
                //좌표가 범위를 넘는지 확인한다.
                if (curPoint.x < 0 || curPoint.y < 0 || curPoint.x >= N || curPoint.y >= M) continue;
                //좌표값을 확인한다.
                if (map[curPoint.x][curPoint.y] != 1) continue;
                
                //방문을 표시한다.
                map[curPoint.x][curPoint.y] = 2;
                //상, 하, 좌, 우 좌표를 queue에 담는다.
                for (int j = 0; j < 4; j++) {
                    queue.offer(new Point(curPoint.x + dx[j], curPoint.y + dy[j]));
                }
                
                //목표점 도착을 확인한다.
                if (curPoint.x == N - 1 && curPoint.y == M -1) return level;
            }
            level++;
        }
        return level;
    }
}