백준 11909 - 배열 탈출

문제

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

리뷰

다익스트라를 이용하여 풀이할 수 있는 간단한 문제였다.

문제에서 한 좌표에서 이동할 수 있는 위치는 가로로 한 칸, 세로로 한 칸이다.
이에 맞추어 다익스트라내에서 좌표별 비용을 갱신하면 되며, 특정 좌표에서의
가능한 경로로 이동할 시 비용의 정의($C$)는 아래와 같다.

로직은 map에 각 좌표별 값을 저장하고 dist 2차원 배열을 설정하여
최대값(Integer.MAX_VALUE)로 초기화한 후 시작 정점에서부터 탐색을
진행하며 dist[N-1][N-1]에 최단 경로 비용을 갱신하도록 구성하였다.

시간 복잡도는 다익스트라의 $O(ElogV)$로 수렴하고 이는 문제에서
$O(2N^2log(N^2))$의 형태이므로 $N=2,222$인 최악의 경우에도 무난히
제한 조건 2초를 통과한다.

코드

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

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[][] map;
    static int[][] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = parseInt(br.readLine());
        map = new int[N][N];
        dist = new int[N][N];

        StringTokenizer st;
        for (int y = 0; y < N; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < N; x++)
                map[y][x] = parseInt(st.nextToken());
        }

        dijkstra();
        System.out.println(dist[N - 1][N - 1]);
        br.close();
    }

    public static void dijkstra() {
        int[] dx = {1, 0};
        int[] dy = {0, 1};

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.w));
        for (int[] ints : dist) Arrays.fill(ints, MAX_VALUE);
        dist[0][0] = 0;
        pq.offer(new Node(0, 0, dist[0][0]));

        int nx, ny, w;
        while (!pq.isEmpty()) {
            Node n = pq.poll();

            if (dist[n.y][n.x] < n.w) continue;

            for (int i = 0; i < dx.length; i++) {
                nx = n.x + dx[i];
                ny = n.y + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

                w = map[ny][nx] - map[n.y][n.x] + 1;
                if (w <= 0) w = 0;

                if (dist[ny][nx] > n.w + w) {
                    dist[ny][nx] = n.w + w;
                    pq.offer(new Node(nx, ny, dist[ny][nx]));
                }
            }
        }
    }

    static class Node {
        int x, y, w;

        public Node(int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }

}

결과