백준 22116번
https://www.acmicpc.net/problem/22116

문제

---

생각하기

---

• 다익스트라 문제이다.
  

동작

결과

코드

---

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final int INF = Integer.MAX_VALUE;
    private static int N;
    private static int[][] map;
    private static int[] dirX = {0, 0, -1, 1};
    private static int[] dirY = {-1, 1, 0, 0};

    private static class Coordinate implements Comparable<Coordinate> {
        int x;
        int y;
        int slope;

        private Coordinate(int x, int y, int slope) {
            this.x = x;
            this.y = y;
            this.slope = slope;
        }

        @Override
        public int compareTo(Coordinate o) {
            return slope - o.slope;
        }
    } // End of Coordinate class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(dijkstra());
        return sb.toString();
    } // End of solve()

    private static long dijkstra() {
        PriorityQueue<Coordinate> pQue = new PriorityQueue<>();
        int[][] maxSlopes = new int[N][N];
        boolean[][] isVisited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            Arrays.fill(maxSlopes[i], INF);
        }

        maxSlopes[0][0] = 0;
        pQue.offer(new Coordinate(0, 0, 0));

        while (!pQue.isEmpty()) {
            Coordinate current = pQue.poll();

            if (maxSlopes[current.x][current.y] < current.slope) continue;
            if (isVisited[current.x][current.y]) continue;
            isVisited[current.x][current.y] = true;

            for (int i = 0; i < 4; i++) {
                int nextX = dirX[i] + current.x;
                int nextY = dirY[i] + current.y;

                if (!isAbleCheck(nextX, nextY, isVisited)) continue;

                int nextSlope = Math.max(current.slope, Math.abs(map[current.x][current.y] - map[nextX][nextY]));

                if (maxSlopes[nextX][nextY] > nextSlope) {
                    maxSlopes[nextX][nextY] = nextSlope;
                    pQue.offer(new Coordinate(nextX, nextY, nextSlope));
                }
            }
        }

        return maxSlopes[N - 1][N - 1];
    } // End of dijkstra()

    private static boolean isAbleCheck(int nextX, int nextY, boolean[][] isVisited) {
        return nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && !isVisited[nextX][nextY];
    } // End of isAbleCheck()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    } // End of input()
} // End of Main class