[백준] 20926번 : 얼음 미로 Gold 2(골드 2) - JAVA[자바]

[Gold II] 얼음 미로 - 20926

문제 링크

성능 요약

메모리: 24316 KB, 시간: 280 ms

분류

데이크스트라, 그래프 이론, 구현, 최단 경로

제출 일자

2024년 6월 3일 10:37:42

문제 설명

탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 멈출 수 없고 왼쪽 바위에 부딪힐 때까지 미끄러진다. 얼음 미로 바깥은 절벽이기 때문에 빠지면 탈출할 수 없다.

얼음 미로에는 4가지 오브젝트가 있다.

1. 테라 : 얼음 미로에 갇힌 탐험가. 상하좌우 4방향으로 이동할 수 있다. 얼음 미로에 단 1명의 테라만 존재한다. 테라가 최초 위치한 빙판의 미끌 시간은 0이다.
2. 바위 : 통과할 수 없다. 미끄러지다 부딪히면 앞에서 멈춘다.
3. 구멍 : 이곳에 빠지면 영영 탈출할 수 없다.
4. 출구 : 이곳에 방문하는 즉시 얼음 미로를 탈출한다. 얼음 미로에 단 1개의 출구만 존재한다.

어떤 빙판 위에서 미끄러지는 데 걸리는 시간을 미끌 시간이라고 하자. 각 빙판마다 미끌 시간은 다를 수 있다.

테라가 어느 한쪽 방향으로 이동할 때, 테라가 미끄러지는 동안 위치한 빙판의 미끌 시간을 더하면 이동 시간을 구할 수 있다. 단, 이동 시간 계산과 관련하여 두 가지 규칙이 있다.

• 테라가 어느 한쪽 방향으로 이동을 시작할 때, 시작 빙판의 미끌 시간은 포함하지 않는다.
• 테라가 출구로 들어갈 때, 출구 빙판의 미끌 시간은 포함하지 않는다.

위 그림에서 테라가 위로 이동할 때의 이동 시간을 계산하자. 테라가 현재 서 있는, 시작 빙판의 미끌 시간 4와 출구 빙판의 미끌 시간 0을 제외하면 1+2 = 3만큼의 시간이 걸린 뒤 출구를 통해 탈출함을 알 수 있다.

저체온증이 시작된 테라는 얼음 미로를 가능한 한 빨리 탈출하고 싶다. 얼음 미로를 탈출하는 데 걸리는 최단 시간을 계산하자.

입력

첫 번째 줄에는 얼음 미로의 가로 크기를 나타내는 정수 W(2≤W≤500), 세로 크기를 나타내는 정수 H(2≤H≤500)가 주어진다.

두 번째 줄부터 H개의 줄에 걸쳐 얼음 미로에 대한 정보가 주어진다.

테라는 T, 바위는 R, 구멍은 H, 출구는 E로 나타낸다.

빙판의 미끌 시간 t는 0 이상 9 이하의 정수로 나타낸다.

출력

얼음 미로를 탈출할 수 있다면 최단 탈출 시간을 출력한다.

얼음 미로를 탈출할 수 없다면 -1을 출력한다.

 

접근 방법

1. 다익스트라를 이용한다.

2. 맵 밖으로 나가거나 구멍에 떨어지는 경우는 기록하지 않는다.

3. 돌에 부딪히는 위치와 EndPoint만 기억하여 기록할 수 있도록 한다.

 

풀이 코드

import java.io.*;
import java.util.*;

/**
 * 문제 : Main_20926_얼음 미로 G2
 */
public class Main {
    // 비용과 위치 좌표를 갖고 있는 Point Class
    static class Point implements Comparable<Point> {
        int x;
        int y;
        int weight;

        public Point(int x, int y, int weight) {
            this.x = x;
            this.y = y;
            this.weight = weight;
        }

        @Override
        public int compareTo(Point o) {
            return this.weight - o.weight;
        }
    }

    // 맵의 위치로 오는데에 비용을 기억하는 map, 각 이동 비용을 기억하는 weight
    static int[][] map, weight;
    // End Point
    static Point e;
    static int W, H;
    static int[] dirX = {-1, 0, 1, 0};
    static int[] dirY = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new int[H][W];
        weight = new int[H][W];

        // Input
        Point s = new Point(0, 0, 0);
        e = new Point(0, 0, 0);
        for (int i = 0; i < H; i++) {
            String input = br.readLine();
            for (int j = 0; j < W; j++) {
                char ch = input.charAt(j);
                map[i][j] = Integer.MAX_VALUE;
                if (ch == 'R') {
                    map[i][j] = -1;
                } else if (ch == 'H') {
                    map[i][j] = -2;
                } else if (ch >= '0' && ch <= '9') {
                    weight[i][j] = ch - '0';
                } else if (ch == 'T') {
                    map[i][j] = 0;
                    s.x = i;
                    s.y = j;
                } else if (ch == 'E') {
                    e.x = i;
                    e.y = j;
                }
            }
        }// Input End

        dijkstra(s);
        System.out.println(map[e.x][e.y] == Integer.MAX_VALUE ? -1 : map[e.x][e.y]);
    }

    private static void dijkstra(Point s) {
        PriorityQueue<Point> queue = new PriorityQueue<>();
        queue.add(s);

        while (!queue.isEmpty()) {
            Point cur = queue.poll();

            // 현재 가지고 있는 비용보다 다음 위치가 더 비싸다면 이동하지 않음
            if (map[cur.x][cur.y] < cur.weight) {
                continue;
            }
            for (int i = 0; i < 4; i++) {
                // 다음 위치를 가져옴
                Point next = getNextPosition(cur, i);

                if (next == null) {
                    continue;
                }
                if (map[next.x][next.y] > next.weight) {
                    map[next.x][next.y] = next.weight;
                    queue.add(next);
                }
            }
        }
    }

    // 다음 위치를 가져오는 메서드
    private static Point getNextPosition(Point cur, int d) {
        Point next = new Point(cur.x, cur.y, cur.weight);
        while (true) {
            int nX = next.x + dirX[d];
            int nY = next.y + dirY[d];
            // 배열 밖이거나 구멍이라면 null 리턴
            if (!isIn(nX, nY) || map[nX][nY] == -2) {
                return null;
            }
            // 바위를 만나면 next 위치 리턴
            else if (map[nX][nY] == -1) {
                return next;
            }
            // 다음 위치 갱신
            next.x = nX;
            next.y = nY;
            next.weight += weight[nX][nY];
            // End Point라면 종료
            if (nX == e.x && nY == e.y) {
                map[nY][nX] = Math.min(next.weight, map[nX][nY]);
                return null;
            }
        }
    }

    private static boolean isIn(int x, int y) {
        return x >= 0 && x < H && y >= 0 && y < W;
    }
}

 

티어에 비해서 난이도가 낮은 문제