6-9: 목수의 미로 탈출

목수의 미로 탈출

 

문제

---

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 찾으려 한다. 그런데 목수는 도끼 하나를 갖고 있으며, 이 도끼를 이용하여 벽을 깨부술 수 있다. 하지만 이 도끼는 내구성이 그렇게 좋지 않기 때문에, 벽을 최대 1개밖에 깰 수 없다. 목수가 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 물론, 벽은 최대 1개까지 깰 수 있다. 아래 예제의 경우 ‘X’ 로 표시된 벽을 깰 경우 거리 18만에 출발점에서 도착점으로 이동할 수 있다.

 

입력

---

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

출력

---

첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 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

예제 출력

18

 

예제 입력

10 10
0 0 0 0 0 0 1 1 0 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 0 0 0 0 0 0 1 1 0
0 0 1 1 1 1 0 1 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 1 0 0
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0

예제 출력

22

import java.util.*;

public class MazeMinPathWithAxe {
//    private static HashSet<Point> seen = new HashSet<>();

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

    public static boolean[][] visited;
    public static boolean[][] visited_broken;

    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];
        visited = new boolean[N][M];
        visited_broken = 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){

        }


        int p = getMinSteps(maze);

        System.out.println(p);

    }

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

    }

    private static int 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;
        int count = 0;

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

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

            if (x == endX && y ==endY){
                return curPos.minDistance;
            }

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

        }
        return 0;
    }


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

        Point p;

        //up
        if (maze[x][y] ==0){
            p = new Point(x, y, parent.isBroken, parent.minDistance+1);
        } else if (!parent.isBroken){
            p = new Point(x, y, true, parent.minDistance+1);
        } else  return;


        if (p.isBroken && !visited_broken[x][y]){
            q.add(p);
            visited_broken[x][y] = true;
        } else if(!p.isBroken && !visited[x][y]){
            q.add(p);
            visited[x][y]= true;
        }



    }


}