백준 9505 - 엔터프라이즈호 탈출

문제

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

리뷰

다익스트라로 풀이할 수 있는 간단한 문제였다.

전투선 클래스 이름에 따라 각 위치별 비용을 설정하기 위해 map H x W 배열을
설정하였고, costMap 자료구조를 통하여 이름과 비용 관계를 저장하였다.

테스트케이스별로 costMap 과 map 에 입력값을 저장하고, 다익스트라를 돌리며
최소 비용으로 인덱스가 배열을 벗어날 경우를 minCost에 갱신하여 답을 도출하였다.

정점의 개수 $V=W \times H$이고, 간선의 개수 $E=4 \times W \times H$ 이므로
다익스트라 로직의 시간복잡도는 $O(4WH \log WH)$가 된다. 따라서 $T=100$,
$W=H=1000$인 최악의 경우에도 제한 조건 10초를 무난히 통과할 수 있다.

코드

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

import static java.lang.Integer.parseInt;
import static java.lang.Long.MAX_VALUE;


public class Main {
    static long[][] map;

    static long[][] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = parseInt(br.readLine());

        StringTokenizer st;
        int K, W, H;
        Character type;
        long w;
        Map<Character, Long> costMap = new HashMap<>();
        int sx, sy;
        sx = sy = 0;
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            K = parseInt(st.nextToken());
            W = parseInt(st.nextToken());
            H = parseInt(st.nextToken());

            map = new long[H][W];
            dist = new long[H][W];

            while (K-- > 0) {
                st = new StringTokenizer(br.readLine());
                type = st.nextToken().charAt(0);
                w = Long.parseLong(st.nextToken());

                costMap.put(type, w);
            }

            String line;
            for (int y = 0; y < H; y++) {
                line = br.readLine();
                for (int x = 0; x < W; x++) {
                    Character key = line.charAt(x);

                    if (key.equals('E')) {
                        sx = x;
                        sy = y;
                        map[y][x] = 0;
                        continue;
                    }

                    map[y][x] = costMap.get(key);
                }
            }

            long result = dijkstra(sx, sy, W, H);
            sb.append(result).append("\n");
            costMap.clear();
        }

        System.out.print(sb);
        br.close();
    }

    static void initDist() {
        for (long[] longs : dist) Arrays.fill(longs, MAX_VALUE);
    }


    static long dijkstra(int sx, int sy, int W, int H) {
        initDist();
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(n -> n.w));
        dist[sy][sx] = 0;
        pq.offer(new Node(sx, sy, dist[sy][sx]));

        long minCost = MAX_VALUE;
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int nx, ny;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (dist[cur.y][cur.x] < cur.w)
                continue;

            for (int i = 0; i < dx.length; i++) {
                nx = cur.x + dx[i];
                ny = cur.y + dy[i];

                if (nx < 0 || nx >= W || ny < 0 || ny >= H) {
                    minCost = Math.min(minCost, cur.w);
                    continue;
                }

                if (dist[ny][nx] > dist[cur.y][cur.x] + map[ny][nx]) {
                    dist[ny][nx] = dist[cur.y][cur.x] + map[ny][nx];
                    pq.offer(new Node(nx, ny, dist[ny][nx]));
                }
            }

        }

        return minCost;
    }


    static class Node {
        int x, y;
        long w;

        public Node(int x, int y, long w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }
}

결과