[JAVA] 백준 1584 - 게임

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

500*500 사이즈의 맵에서 위험구역(생명력-1), 죽음의구역(진입불가)를 거쳐 500,500에 도달했을 때 필요한 최소 생명수를 구하는 문제이다.

map에 0 -> 안전, 1 -> 위험, 2-> 죽음으로 표시해놓고 다익스트라를 위한 우선순위큐를 map의 flag 기준으로 정렬해 구했다. 우선순위큐 타입은 int[]로 했는데, 처음에 i, j, map flag로 구성했다가 메모리 초과가 나서 i,j,누적 소비 생명으로 바꾸고 통과했다.

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

import static java.util.Comparator.comparingInt;

public class Main {
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] map = new int[501][501];
        int[][] weight = new int[501][501];
        for (int i = 0; i < weight.length; i++) {
            Arrays.fill(weight[i], Integer.MAX_VALUE);
        }
        weight[0][0] = 0;
        int dCount = par(br.readLine());
        for (int i = 0; i < dCount; i++) {
            int[] danger = getArray(br.readLine());
            int x1 = danger[0];
            int x2 = danger[2];
            int y1 = danger[1];
            int y2 = danger[3];

            for (int j = Math.min(x1,x2); j <= Math.max(x1,x2) ; j++) {
                for (int k = Math.min(y1,y2); k <= Math.max(y1,y2); k++) {
                    map[j][k] = 1;
                }
            }
        }

        int deathCount = par(br.readLine());
        for (int i = 0; i < deathCount; i++) {
            int[] danger = getArray(br.readLine());
            int x1 = danger[0];
            int x2 = danger[2];
            int y1 = danger[1];
            int y2 = danger[3];
            for (int j = Math.min(x1,x2); j <= Math.max(x1,x2) ; j++) {
                for (int k = Math.min(y1,y2); k <= Math.max(y1,y2); k++) {
                    map[j][k] = Math.max(map[j][k],2);
                }
            }
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(comparingInt(arr -> arr[2]));
        pq.offer(new int[]{0,0,0});
        while(!pq.isEmpty()){
            int[] target = pq.poll();
            int i = target[0];
            int j = target[1];
            int lives = target[2];
            if(i==500&&j==500){
                System.out.println(lives);
                return;
            }
            for (int k = 0; k < 4; k++) {
                if(check(map,i+dx[k], j+dy[k])){
                    int life = map[i+dx[k]][j+dy[k]];
                    if(lives + life < weight[i+dx[k]][j+dy[k]]){
                        weight[i+dx[k]][j+dy[k]] = lives + life;
                        pq.offer(new int[]{i+dx[k],j+dy[k], lives + life});
                    }
                }
            }
        }
        System.out.println(-1);
    }
    static boolean check(int[][] map, int i, int j){
        if(i<0||i>=map.length) return false;
        if(j<0||j>=map.length) return false;
        if(map[i][j]==2) 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();
    }
}