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

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

N개의 테스트 케이스가 주어지고, <알파벳, 가중치> 정보와 Map이 주어졌을 때, E에서 시작해 가장자리로 이동할 때 가중치가 최소값이 얼마인지 출력하는 문제이다.

HashMap에 간선 정보를 저장 후 다익스트라로 E에서 모든 노드까지의 최단 경로를 구한 후 가장자리의 최솟값을 구했다.

반복문 Index를 헷갈려서 시간을 잡아먹었다,,

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = par(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < tc; i++) {
            int[] info = getArray(br.readLine());
            HashMap<String, Integer> map = new HashMap<>();
            int vertexCount = info[0];
            for (int j = 0; j < vertexCount; j++) {
                String[] temp = br.readLine().split(" ");
                map.put(temp[0], par(temp[1]));
            }
            int width = info[1];
            int height = info[2];
            char[][] arr = new char[height][width];
            int[][] dist = new int[height][width];
            boolean[][] visited = new boolean[height][width];
            for (int j = 0; j < height; j++) {
                arr[j] = br.readLine().toCharArray();
                Arrays.fill(dist[j], Integer.MAX_VALUE);
            }
            Class start = new Class();
            for (int j = 0; j < height; j++) {
                for (int k = 0; k < width; k++) {
                    if (arr[j][k] == 'E') {
                        dist[j][k] = 0;
                        start.i = j;
                        start.j = k;
                    }
                }
            }
            PriorityQueue<Class> pq = new PriorityQueue<>();
            pq.offer(start);
            while (!pq.isEmpty()) {
                Class c = pq.poll();
                int h = c.i;
                int w = c.j;
                int weight = c.weight;
                if (visited[h][w]) continue;
                visited[h][w] = true;
                for (int j = 0; j < 4; j++) {
                    int th = h + dx[j];
                    int tw = w + dy[j];
                    if (check(th, tw, arr, visited)) {
                        if (dist[th][tw] > weight + map.get(String.valueOf(arr[th][tw]))) {
                            dist[th][tw] = weight + map.get(String.valueOf(arr[th][tw]));
                            Class offer = new Class(th, tw);
                            offer.weight = dist[th][tw];
                            pq.offer(offer);
                        }
                    }
                }
            }
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < width; j++) {
                min = Math.min(min, dist[0][j]);
                min = Math.min(min, dist[height - 1][j]);
            }
            for (int j = 0; j < height; j++) {
                min = Math.min(min, dist[j][0]);
                min = Math.min(min, dist[j][width - 1]);
            }
            sb.append(min);
            if (i != tc - 1) sb.append("\n");
        }
        System.out.println(sb);
    }

    static boolean check(int i, int j, char[][] map, boolean[][] visited) {
        if (i < 0 || i >= map.length) return false;
        if (j < 0 || j >= map[0].length) return false;
        if (visited[i][j]) return false;
        if (map[i][j] == 'E') return false;
        return true;
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Class implements Comparable<Class> {
    int i;
    int j;
    int weight = 0;

    Class(int i, int j) {
        this.i = i;
        this.j = j;
    }

    Class() {
    }

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