[BaekJoon] 20926 얼음 미로 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int width;
    static int height;
    static int[] tera;
    static int[] exit;
    static int[][] maze;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    static void input() {
        Reader scanner = new Reader();

        width = scanner.nextInt();
        height = scanner.nextInt();
        maze = new int[height][width];

        for (int row = 0; row < height; row++) {
            String info = scanner.nextLine();
            for (int col = 0; col < width; col++) {
                if (Character.isDigit(info.charAt(col))) {
                    maze[row][col] = info.charAt(col) - '0';
                } else {
                    if (info.charAt(col) == 'T') {
                        tera = new int[]{row, col};
                    } else {
                        if (info.charAt(col) == 'R') {
                            maze[row][col] = -1;
                        }
                        if (info.charAt(col) == 'H') {
                            maze[row][col] = -2;
                        }
                        if (info.charAt(col) == 'E') {
                            exit = new int[]{row, col};
                            maze[row][col] = -3;
                        }
                    }
                }
            }
        }
    }

    /*
     * 미로 상태는 숫자와 문자로 이루어져있는데 미끌 시간을 계산하기 위해서는 숫자가 필요하기 때문에 문자 역시 숫자로 바꿔 미로 상태를 표기한다
     *  - T(테라) : 빈칸(0), R(바위) : -1, H(구멍) : -2, E(출구) : -3
     * 다익스트라를 통해 테라를 이동시켜보며 최단 시간을 구한다
     *  - 테라가 있는 곳에서 상하좌우 각 방향으로 계속 이동하다가
     *      - 구멍을 만나거나 얼음 미로의 밖으로 나간다면 해당 방향으로는 이동할 수 없음을 나타내는 -1을 반환한다
     *      - 바위를 만나면 테라가 있는 곳을 바로 이전 이전 칸으로 옮기고 이동하는 동안 누적한 미끌 시간을 반환한다
     *      - 출구를 만나면 누적한 미끌 시간을 반환한다
     *  - 이동시킨 칸이 출구가 아니고 이동할 수 없는 곳이 아니라면 지금까지의 최소 시간과 지금까지 누적한 미끌 시간을 비교하여
     *    누적한 미끌 시간이 더 작다면 최소 시간을 누적 시간으로 갱신하고 Queue에 해당 정보를 넣어 다음 이동을 탐색한다
     * 다익스트라를 모두 돌린 후에 최단 시간을 나타내느 2차원 배열에서 출구칸 값이 답이 된다
     */
    static void solution() {
        int time = dijkstra();
        if (time == Integer.MAX_VALUE) {
            System.out.println(-1);
            return;
        }
        System.out.println(time);
    }

    static int dijkstra() {
        Queue<Tera> teras = new PriorityQueue<>();
        int[][] times = new int[height][width];
        for (int row = 0; row < height; row++) {
            Arrays.fill(times[row], Integer.MAX_VALUE);
        }

        teras.offer(new Tera(tera[0], tera[1], 0));
        times[tera[0]][tera[1]] = 0;

        while (!teras.isEmpty()) {
            Tera cur = teras.poll();
            if (times[cur.x][cur.y] < cur.time) {
                continue;
            }

            for (int dir = 0; dir < dx.length; dir++) {
                int[] tera = new int[]{cur.x, cur.y};
                int moveTime = move(dir, tera);
                if (moveTime == -1) {
                    continue;
                }

                int nextTime = cur.time + moveTime;
                if (times[tera[0]][tera[1]] > nextTime) {
                    times[tera[0]][tera[1]] = nextTime;
                    teras.offer(new Tera(tera[0], tera[1], nextTime));
                }
            }
        }

        return times[exit[0]][exit[1]];
    }

    static int move(int dir, int[] tera) {
        int totalTime = 0;
        while (true) {
            tera[0] += dx[dir];
            tera[1] += dy[dir];
            if (!isInMap(tera[0], tera[1]) || maze[tera[0]][tera[1]] == -2) {
                tera[0] -= dx[dir];
                tera[1] -= dy[dir];
                return -1;
            }
            if (maze[tera[0]][tera[1]] == -1) {
                tera[0] -= dx[dir];
                tera[1] -= dy[dir];
                break;
            }
            if (maze[tera[0]][tera[1]] == -3) {
                break;
            }

            totalTime += maze[tera[0]][tera[1]];
        }

        return totalTime;
    }

    static boolean isInMap(int x, int y) {
        return x >= 0 && x < height && y >= 0 && y < width;
    }

    static class Tera implements Comparable<Tera> {
        int x;
        int y;
        int time;

        public Tera(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }

        @Override
        public String toString() {
            return "Tera{" +
                    "x=" + x +
                    ", y=" + y +
                    ", time=" + time +
                    '}';
        }

        @Override
        public int compareTo(Tera o) {
            return time - o.time;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}