6-5: 미로찾기

미로찾기

 

문제

---

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 출력하는 프로그램을 작성하시오. 아래 그림에 대하여 S에서 E까지 가는 최단거리는 22이다.

 

입력

---

첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 1은 이동할 수 없는 부분을 나타낸다.

 

출력

---

(N-1, 0) 에서 출발하여 (0, M-1) 까지 이동하는 데 필요한 최단거리를 출력한다.

 

예제 입력

10 10
0 0 0 0 0 0 1 1 0 0
0 1 1 1 0 0 1 0 1 0
0 1 1 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0
0 0 1 1 1 1 0 0 1 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 0 1 1 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 0

예제 출력

22

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class MazeMinPathThird {
    /**
     *
     * 아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다.
     * 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 출력하는 프로그램을 작성하시오. 아래 그림에 대하여 S에서 E까지 가는 최단거리는 22이다.
     *
     *
     *
     *
     * @param args
     */
    public static boolean visited[][] ;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int maze[][] = new int[N][M];
//        int distance[][] = new int[N][M];
        visited = new boolean[N][M];

        try{
            for (int i=0; i<N; i++){
                for (int j=0; j<M; j++){
                    maze[i][j] = sc.nextInt();
                }
            }
        } catch (NoSuchElementException e){

        }


        getMinSteps(maze);

    }

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

    private static void getMinSteps (int[][] maze) {

        LinkedList<Point> queue = new LinkedList<>();
        int startX =maze.length-1;
        int startY = 0;
        int endX = 0;
        int endY = maze[0].length-1;

        Point p =new Point(startX, startY, 0);
        queue.add(p);

        while (!queue.isEmpty()){
            Point curPos = queue.remove();
            int x = curPos.x;
            int y= curPos.y;
            visited[x][y] = true;

            if (curPos.x == endX && curPos.y == endY){
                System.out.println(curPos.minD);
                return;
            }

            tryNext(queue, maze, x-1, y, x, y, curPos.minD);
            tryNext(queue, maze, x+1, y, x, y, curPos.minD);
            tryNext(queue, maze, x, y-1, x, y, curPos.minD);
            tryNext(queue, maze, x, y+1, x, y, curPos.minD);


        }
    }

    private static void tryNext(LinkedList<Point> queue, int[][] maze, int x, int y, int origX, int origY, int origD) {
        if (x<0 || x>=maze.length || y<0 || y>=maze[0].length){
            return;
        }

        if (maze[x][y] ==0 && !visited[x][y]){
            Point p2 = new Point(x, y, 1 + origD);
            queue.add(p2);
            visited[x][y] = true;
        }

    }

}