백준 14923번 미로 탈출 [JAVA]

문제

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

 

 

입력

 

 

출력

D (탈출 할 수 없다면, -1을 출력한다.)

 

 

예제

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_BJ_14923_미로탈출 {
    static int N, M, Hx, Hy, Ex, Ey, ans = Integer.MAX_VALUE;
    static int map[][];
    static boolean[][][] visited;
    static PriorityQueue<info> queue = new PriorityQueue<>(new Comparator<info>() {
 
        @Override
        public int compare(info o1, info o2) {
            // TODO Auto-generated method stub
            return o1.dis-o2.dis;
        }
    });
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][M];
        visited = new boolean[2][N][M];
 
        st = new StringTokenizer(br.readLine(), " ");
        Hx = Integer.parseInt(st.nextToken())-1;
        Hy = Integer.parseInt(st.nextToken())-1;
 
        queue.offer(new info ( Hx, Hy, 0, 0 ));
 
        st = new StringTokenizer(br.readLine(), " ");
 
        Ex = Integer.parseInt(st.nextToken());
        Ey = Integer.parseInt(st.nextToken());
 
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<M;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        bfs();
        System.out.println(ans==Integer.MAX_VALUE? -1 : ans);
 
    }
 
    public static void bfs() {
        visited[0][Hx][Hy] = true;
        
        while (!queue.isEmpty()) {
            info info = queue.poll();
            
            if (info.x == Ex-1 && info.y == Ey-1) {
                ans = info.dis;
                return;
            }
 
            for (int i = 0; i < 4; i++) {
                int nx = info.x + dx[i];
                int ny = info.y + dy[i];
 
                if (range(nx, ny)) {
 
                    if (map[nx][ny] == 0 && !visited[info.cnt][nx][ny]) { 
                        visited[info.cnt][nx][ny] = true;
                        queue.offer(new info( nx, ny, info.cnt, info.dis+1 ));
                        
                    } else if (map[nx][ny] == 1 && info.cnt==0) {
                        visited[1][nx][ny] = true;
                        queue.offer(new info ( nx, ny, 1, info.dis+1));
                    }
                }
            }
 
        }
    }
 
    public static boolean range(int x, int y) {
        return x >= 0 && y >= 0 && x <N && y <M;
    }
    
    public static class info{
        int x, y, cnt, dis;
 
        public info(int x, int y, int cnt, int dis) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.dis = dis;
        }
        
    }
 
}

풀이 방법

미로에서 탈출할 수 있는 가장 빠른 경로 거리를 구하는 문제였습니다. 미로 안에는 벽을 길로 만들 수 있는 지팡이가 존재하기 때문에 3차원 배열을 이용해 문제를 풀었습니다. 지팡이는 한 번만 사용할 수 있기 때문에 만약에 지팡이를 사용하지 않았다면 길 혹은 벽으로 이동할 수 있고, 반대로 지팡이를 이전에 사용했더라면 길인 경우에만 이동할 수 있도록 해주었습니다. 그리고 탈출 위치에 도착했다면 거리를 리턴해주고 출력해주었습니다.