[백준 14923] 미로 탈출 -JAVA //le_effort

미로 탈출

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	1512	523	385	35.000%

문제

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

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

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

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

입력

xxxxxxxxxx
N M
Hx Hy
Ex Ey
N X M 행렬

• 2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000
• 1 ≤ Hx, Hy, Ex, Ey ≤ 1000
• (Hx, Hy)≠ (Ex, Ey)
• 행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

출력

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

예제 입력 1 복사

xxxxxxxxxx
5 6
1 1
5 6
0 1 1 1 0 0
0 1 1 0 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 0 0 1 1 0

예제 출력 1 복사

11

 

 

 

풀이

이 문제를 풀다보니 알고리즘을 시작 한 지 얼마 안됐을때가 생각이 났다.

이런 문제를 풀면서 이거 어떻게 풀지 남들 코드 봐도 이해가 잘 안가고

그랬는데 10분만에 한 번에 풀어서 기분이 좋다 ㅎㅎ

 

이 문제의 핵심인 '벽을 부수고 이동하는 것' 이것만 잘 구현해주면 된다.

 

class Node implements Comparable<Node>{
    int x,y,dist,flag;
    Node(int x, int y, int dist, int flag){
        this.x=x;
        this.y=y;
        this.dist = dist;
        this.flag= flag;
    }
    public int compareTo(Node o) {
        return this.dist-o.dist;
    }
}

x,y는 해당 좌표이고 dist는 거리

이제 중요한 flag 라는 변수가 나온다

flag가 0이면 벽을 한 번도 안부순상태

flag가 1이면 벽을 부순 상태

이걸 분기별로 잘 처리해주면 된다

visited는 3차원으로 설정해

visited[x] [y] [0]

visited[x] [y] [1]

0일 경우 이전에 벽을 안부수고 해당 위치에 도달 할 경우

1일 경우 이전에 혹은 이번에 벽을 부수고 해당 위치에 도달 하는 경우

이것만 구현 해주면 된다.

 

그리고 우선순위큐를 사용해 거리가 작은것부터 나오게 했으니

visited [x] [y] [0] 혹은 1에는 최단거리가 들어오게 된다.

 

전체코드

import java.io.*;
import java.util.*;
public class Main {
    static int n,m;
    static int end_x ,end_y,start_x,start_y;
    static int map[][];
    static boolean visited[][][];
    static int ans = Integer.MAX_VALUE;
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        String [] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        
        map = new int[n+1][m+1];
        visited = new boolean[n+1][m+1][2];
        
        String[] tt = br.readLine().split(" ");
        start_x = Integer.parseInt(tt[0]);
        start_y = Integer.parseInt(tt[1]);
        
        String[] ttt = br.readLine().split(" ");
        end_x = Integer.parseInt(ttt[0]);
        end_y = Integer.parseInt(ttt[1]);
        
        for(int i=1; i<=n; i++) {
            String [] input = br.readLine().split(" ");
            for(int j=1; j<=m; j++) {
                map[i][j] = Integer.parseInt(input[j-1]);
            }
        }
        bfs();
        if(ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        }
        else {
            System.out.println(ans);
        }
    }
    public static void bfs() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start_x,start_y,0,0));
        while(!q.isEmpty()) {
            Node a=  q.poll();
            
            if(a.x == end_x && a.y ==end_y) {
                ans = a.dist;
                break;
            }
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(isRange(nx,ny)) {
                    if(map[nx][ny]==0 && !visited[nx][ny][a.flag]) {
                        q.add(new Node(nx,ny,a.dist+1,a.flag));
                        visited[nx][ny][a.flag] = true;
                    }
                    else if(a.flag ==0 && map[nx][ny]==1 && !visited[nx][ny][1]) {
                        q.add(new Node(nx,ny,a.dist+1,1));
                        visited[nx][ny][1] = true;
                    }
                }
                
            }
            
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=1 && y>=1 && x<=n && y<=m) {
            return true;
        }
        return false;
    }
}
class Node implements Comparable<Node>{
    int x,y,dist,flag;
    Node(int x, int y, int dist, int flag){
        this.x=x;
        this.y=y;
        this.dist = dist;
        this.flag= flag;
    }
    public int compareTo(Node o) {
        return this.dist-o.dist;
    }
}