[JAVA] 백준 11909 - 배열 탈출

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

N X N 크기의 2차원 배열에서 0,0 에서 N-1, N-1 까지 가는 최소 비용을 구하는 문제인데, 사진의 이동조건과 + 배열의 값이 작은 쪽으로만 이동이 가능해서 버튼을 눌러(회당 1원) 현재 위치의 값을 이동하려고 하는 쪽의 값보다  크게 만든 후 이동해야 할 때, 종료점에 도달하는 최소비용을 구하는 문제이다.

 

지문에서 주어진 조건에 따라 분기하면서 비용을 최소로 하는 경로를 구했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = par(br.readLine());
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            map[i] = getArray(br.readLine());
        }
        boolean[][] visited = new boolean[n][n];
        PriorityQueue<Index> pq = new PriorityQueue<>();
        Index start = new Index(map[0][0],0,0);
        start.cost = 0;
        pq.offer(start);
        int ans = Integer.MAX_VALUE;
        while(!pq.isEmpty()){
            Index target = pq.poll();
            int value = target.value;
            int i = target.i;
            int j = target.j;
            int cost = target.cost;
            if(visited[i][j]) continue;
            visited[i][j] = true;
            if(i<n-1&&j<n-1){
                if(check(map,i+1,j,visited)){
                    int v = map[i+1][j];
                    if(value<=v){
                        int targetCost = cost+(v-value)+1;
                        Index offer = new Index(v,i+1,j);
                        offer.cost = targetCost;
                        pq.offer(offer);
                    }else{
                        Index offer = new Index(v,i+1,j);
                        offer.cost = cost;
                        pq.offer(offer);
                    }
                }
                if(check(map,i,j+1,visited)){
                    int v = map[i][j+1];
                    if(value<=v){
                        int targetCost = cost+(v-value)+1;
                        Index offer = new Index(v,i,j+1);
                        offer.cost = targetCost;
                        pq.offer(offer);
                    }else{
                        Index offer = new Index(v,i,j+1);
                        offer.cost = cost;
                        pq.offer(offer);
                    }
                }
            }else if(i==n-1&&j<n-1){
                if(check(map,i,j+1,visited)){
                    int v = map[i][j+1];
                    if(value<=v){
                        int targetCost = cost+(v-value)+1;
                        Index offer = new Index(v,i,j+1);
                        offer.cost = targetCost;
                        pq.offer(offer);
                    }else{
                        Index offer = new Index(v,i,j+1);
                        offer.cost = cost;
                        pq.offer(offer);
                    }
                }
            }else if(j==n-1&&i<n-1){
                if(check(map,i+1,j,visited)){
                    int v = map[i+1][j];
                    if(value<=v){
                        int targetCost = cost+(v-value)+1;
                        Index offer = new Index(v,i+1,j);
                        offer.cost = targetCost;
                        pq.offer(offer);
                    }else{
                        Index offer = new Index(v,i+1,j);
                        offer.cost = cost;
                        pq.offer(offer);
                    }
                }
            }else{
                ans = Math.min(ans,cost);
            }
        }

        System.out.println(ans);
    }
    static boolean check(int[][] map, int i, int j, 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;
        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 Index implements Comparable<Index>{
    int value;
    int i;
    int j;
    int cost = Integer.MAX_VALUE;
    Index(int v, int i, int j){
        this.value = v;
        this.i = i;
        this.j = j;
    }

    @Override
    public int compareTo(Index o) {
        return this.cost - o.cost;
    }
}