[JAVA] 백준 22116 - 창영이와 퇴근

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

각 정점별 값 차이를 최소로 하는 경로로 이동할 때, 경로의 값의 최댓값의 최솟값을 구하는 문제이다.

첫번째로 mid 값으로 답을 정해놓고 하는 이분 탐색으로 시도했다가 시간초과를 맞고

우선순위큐 정렬 기준을 경로의 max값으로 지정해놓고 돌렸는데 offer 기준을 최단경로 기준으로 잡아놔서 또 틀렸다가

offer 기준을 값차이의 max값으로 돌린 뒤 정답을 받았다.

괜히 시간을 많이 잡아먹었다.

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = par(br.readLine());
        int[][] map = new int[t][t];
        int[][] dist = new int[t][t];
        for (int i = 0; i < t; i++) {
            map[i] = getArray(br.readLine());
        }
        PriorityQueue<Block22116> pq = new PriorityQueue<>();
        Block22116 start = new Block22116(0, 0, map[0][0]);
        for (int i = 0; i < t; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = 0;
        pq.offer(start);
        while (!pq.isEmpty()) {
            Block22116 poll = pq.poll();
            int i = poll.i;
            int j = poll.j;
            int value = poll.value;
            if (i == t - 1 && j == t - 1) {
                break;
            }
            for (int k = 0; k < 4; k++) {
                int ti = i + dx[k];
                int tj = j + dy[k];
                if (check(ti, tj, t)) {
                    int temp = map[ti][tj];
                    int diff = Math.abs(value - temp);
                    if(dist[ti][tj]>Math.max(dist[i][j],diff)){
                        dist[ti][tj] = Math.max(dist[i][j],diff);
                        Block22116 offer = new Block22116(ti, tj, temp);
                        offer.max = dist[ti][tj];
                        pq.offer(offer);
                    }
                }
            }
        }
        System.out.println(dist[t-1][t-1]);
    }

    static boolean check(int i, int j, int len) {
        if (i < 0 || i >= len) return false;
        if (j < 0 || j >= len) 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 Block22116 implements Comparable<Block22116> {
    int i;
    int j;
    int value;
    int max = 0;

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

    @Override
    public int compareTo(Block22116 o) {
        return this.max - o.max;
    }
}