백준 4485 - 녹색 옷 입은 애가 젤다지?

문제

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

리뷰

다익스트라로 쉽게 풀이할 수 있는 문제였다.

그저 map에 주어진 도둑루피 정보를 전부 저장한 후 다익스트라를 돌리면
dist[N-1][N-1]에 최소 비용이 도출된다.

로직의 시간복잡도는 $O(ElogV)$로 수렴하므로 $N$이 125인 최악의 경우에도
무난히 제한 조건 1초를 통과한다.

코드

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));
        StringTokenizer st;

        int problem = 1;
        StringBuilder sb = new StringBuilder();

        while (true) {
            N = parseInt(br.readLine());

            if (N == 0) break;

            map = new int[N][N];
            dist = new int[N][N];

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

            dijkstra();

            sb.append("Problem " + problem + ": " + dist[N - 1][N - 1]).append("\n");
            problem++;
        }

        System.out.println(sb);
        br.close();
    }

    static boolean isOut(int x, int y) {
        return x < 0 || x >= N || y < 0 || y >= N;
    }

    static void dijkstra() {
        for (int i = 0; i < dist.length; i++)
            Arrays.fill(dist[i], MAX_VALUE);
        dist[0][0] = map[0][0];
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.w));
        pq.offer(new Node(0, 0, dist[0][0]));

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        while (!pq.isEmpty()) {
            Node current = pq.poll();

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

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

                if (isOut(nx, ny))
                    continue;

                if (dist[ny][nx] > current.w + map[ny][nx]) {
                    dist[ny][nx] = current.w + map[ny][nx];
                    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;
        }
    }
}

결과