[백준]20926: 얼음 미로 - JAVA

[백준]20926: 얼음 미로

풀이

🪑 구현 + 다익스트라 문제이다. 

 

 

📝문제의 조건을 정리해보자.

• 얼음 미로에서는 한 방향으로 이동시 바위나 출구를 만날때 까지 멈출 수 없다. 바깥은 절벽이다.
• T: 상하좌우로 이동할 수 있다.
• R: 통과할 수 없으며 부딪히면 멈춘다
• H: 이곳에 빠지면 탈출할 수 없다.
• E: 미로를 탈출하는 유일한 출구이다.
• 각 위치마다 미끌시간이 존재하며 탈출할 수 있는 최단 미끌시간을 구한다.

 

 

🔧 다음과 같은 풀이를 생각해 주었다.

1. 다익스트라를 사용한다.
2. 한번 이동할 때 해당 방향으로 이동할 수 있는지 먼저 확인한다.
3. 이동 가능하면 그 방향으로 갈 수 있는 곳까지 간다.
4. 도착한 후 더 짧은 미끌시간을 계산해 준다.
5. 도착 노드의 최단 미끌시간을 출력한다.

 

📌 처음엔 70 ~ 80프로 쯤에 틀렸었는데, INF 값을 Integer.MAX_VALUE로 변경해주니 통과되었다.

 

 

🔹 다익스트라를 사용한다.

- 최단 거리가 아닌, 최단 미끌시간을 갖는 경로를 계산해 주어야 하므로 단순 BFS로는 풀 수 없다. 다익스트라 알고리즘으로 최단 미끌시간을 저장해 주면서 탐색해 주어야 한다.

- 출발 지점인 T에서 시작하여 모든 노드로 가는 최단 경로를 탐색한다.

- 더 짧은 미끌시간을 가지는 순서대로 탐색을 한다.

 

🔹 한번 이동할 때 해당 방향으로 이동할 수 있는지 먼저 확인한다.

- 단순히 이동만 하는 것이 아니라 이동 하면서 이동 경로에 있는 값이 탐색에 필요하다. 

- 그러므로 일단 해당 방향으로 갈 수 있는지 먼저 확인 후, 갈 수 있을때만 경로에 있는 값을 계산해 준다.

 

🔹 이동 가능하면 그 방향으로 갈 수 잇는 곳까지 간다.

- 그 방향으로 갈 수 있는지 확인하기 위해 현재 위치에서 이동하는 방향으로의 비율을 늘려주며 탐색하였다.

- 가는 동안에 맵의 범위를 벗어나거나, H를 만난다면 갈 수 없는 방향이다.

- 가는 길에 바위를 만나면 그 전까지만 이동 가능한 위치가 된다.

- 가는 길에 출구를 만나면 출구까지 이동 가능한 위치가 된다.

 

🔹도착한 후 더 짧은 미끌시간을 계산해 준다.

- 원래의 미끌시간이랑 비교를 해서 현재 경로까지 이동하는 동안 추가되는 미끌시간과 지금까지 이동하며 추가된 미끌시간의 합 중에 더 작은 값을 저장해 준다.

 

🔹 도착 노드의 최단 미끌시간을 출력한다.

- 탐색할 수 있는 모든 경우가 끝나면 도착 노드의 최단 미끌시간을 출력해 준다.

 

코드

import java.util.*;
 
public class Main {
 
    static char[][] board;
    static int[][] dist;
    static int w, h;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        //입력
        w = scan.nextInt();
        h = scan.nextInt();
        scan.nextLine();
 
        board = new char[h][w];
        int start_x = -1, start_y = -1;
        int end_x = -1, end_y = -1;
        for(int i = 0; i < h; i++) {
            String str = scan.nextLine();
            for(int j = 0; j < w; j++) {
                board[i][j] = str.charAt(j);
                if(board[i][j] == 'T') {
                    start_x = i;
                    start_y = j;
                } else if(board[i][j] == 'E') {
                    end_x = i;
                    end_y = j;
                }
            }
        }
        //입력 끝
 
        int INF = Integer.MAX_VALUE;
        dist = new int[h][w];
        for(int i = 0; i < h; i++) {
            Arrays.fill(dist[i], INF);
        }
 
        bfs(start_x, start_y);
        if(dist[end_x][end_y] == INF) System.out.println("-1");
        else System.out.println(dist[end_x][end_y]);
    }   
 
    public static void bfs(int x, int y) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        boolean[][] visited = new boolean[h][w];
        q.offer(new Node(x, y, 0));
        dist[x][y] = 0;
 
        while(!q.isEmpty()) {
            Node current = q.poll();
        
            if(visited[current.x][current.y]) continue;
            visited[current.x][current.y] = true;
 
            for(int i = 0; i < 4; i++) {
                int go_ratio = can_go(i, current.x, current.y);
                if(go_ratio < 1) continue;
 
                int sum_dist = 0;
                for(int j = 1; j <= go_ratio; j++) {
                    if(board[current.x + dx[i] * j][current.y + dy[i] * j] == 'E') continue;
                    else sum_dist += (board[current.x + dx[i] * j][current.y + dy[i] * j] - '0');
                }
                int nx = current.x + dx[i] * go_ratio;
                int ny = current.y + dy[i] * go_ratio;
 
                if(dist[nx][ny] > sum_dist + current.time) {
                    dist[nx][ny] = sum_dist + current.time;
                    q.offer(new Node(nx, ny, dist[nx][ny]));
                }
            }
        }
    }
 
    public static int can_go(int dir, int x, int y) {
        int ratio = 1;
        while(true) {
            int nx = x + dx[dir] * ratio;
            int ny = y + dy[dir] * ratio;
 
            if(nx < 0 || ny < 0 || nx >= h || ny >= w) break;
            if(board[nx][ny] == 'H') break;
            
            if(board[nx][ny] == 'R') return ratio - 1;
            if(board[nx][ny] == 'E' ) return ratio;
 
            ratio++;
        }
        return -1;
    }
 
    public static class Node implements Comparable<Node>{
        int x;
        int y;
        int time;
 
        public Node(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
 
        @Override
        public int compareTo(Node n) {
            return this.time - n.time;
        }
    }
}