(백준) 얼음 미로 - 20926

https://www.acmicpc.net/problem/20926

20926번: 얼음 미로

 

🐢 해설

시작하는 위치를 플레이어라고 하면 플레이어는 이동할 때 1)나가거나 2) 구멍에 빠지거나 3) 벽에 부딪히거나 4) 탈출하거나 하는 총 4가지 경우로만 이동할 수 있다. 이때 얼음을 타면서 최소한의 시간으로 탈출하는 경우를 찾아야 하는데 이를 위해 큐에 담겨있는 이동하는 플레이어 객체를 소요시간이 낮은 순으로 우선 탐색하기 위해 우선순위 큐를 이용했다.

 

초기 플레이어 위치를 큐에 넣어서 BFS를 돌려주었고 벽인 경우만 멈추고 다시 큐에 넣어줬으며 그외의 경우에는 제외하도록 했다. 이때 탈출구를 지날 경우 그때의 소요시간과 최소 소요시간과 비교해서 갱신하고 제외처리 해주었다.

 

무엇보다 벽에 부딪혀서 움직이지 않는 경우 큐에 넣지 않아야 했고, 방문여부를 얼음을 탈 때는 하지 않고 큐에서 꺼낼때만 확인하고 체크하도록 하는것이 중요했다.

 

🐢 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int Hol = -1, Rock = 100, Exit = 200;
    static int W, H, Min = Integer.MAX_VALUE;
    static int[][] board;
    static Dot Me;
    static boolean[][] visited;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] input = br.readLine().split(" ");
        W = Integer.parseInt(input[0]);
        H = Integer.parseInt(input[1]);
 
        board = new int[H][W];
        visited = new boolean[H][W];
        for (int i = 0; i < H; i++) {
            String l = br.readLine();
            for (int j = 0; j < W; j++) {
                char c = l.charAt(j);
                if (c >= '1' && c <= '9') board[i][j] = c - '0';
                else if (c == 'T') Me = new Dot(i, j, 0);
                else if (c == 'E') board[i][j] = Exit;
                else if (c == 'H') board[i][j] = Hol;
                else if (c == 'R') board[i][j] = Rock;
            }
        }
 
        BFS();
        if (Min == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(Min);
    }
 
    private static void BFS() {
        PriorityQueue<Dot> queue = new PriorityQueue<>(Comparator.comparingInt(d -> d.t));
        queue.add(Me);
 
        while (!queue.isEmpty()) {
            Dot now = queue.poll();
 
            if (visited[now.y][now.x]) continue;
            visited[now.y][now.x] = true;
 
            for (int d = 0; d < 4; d++) {
                Dot dot = iceSliding(now, d);
                if (dot != null) queue.add(dot);
            }
        }
    }
 
    private static Dot iceSliding(Dot now, int d) {
        int ny = now.y;
        int nx = now.x;
        int time = 0;
        boolean flag = false;
 
        while (true) {
            ny += dy[d];
            nx += dx[d];
 
            if (isOut(ny, nx)) break;
            if (board[ny][nx] == Hol) break;
            if (board[ny][nx] == Rock) {
                flag = true;
                break;
            }
            if (board[ny][nx] == Exit) {
                Min = Math.min(Min, now.t + time);
                break;
            }
            time += board[ny][nx];
        }
 
        ny -= dy[d];
        nx -= dx[d];
        if (flag && !(ny == now.y && nx == now.x))
            return new Dot(ny, nx, now.t + time);
        return null;
    }
 
    private static boolean isOut(int ny, int nx) {
        return ny < 0 || nx < 0 || ny >= H || nx >= W;
    }
 
    private static class Dot
    {
        int y, x, t;
 
        public Dot(int y, int x, int t) {
            this.y = y;
            this.x = x;
            this.t = t;
        }
    }
}