녹색 옷 입은 애가 젤다지?

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

풀이

젤다는 납치당하는 것이 취미인 공주고 녹색 옷을 입은 애는 링크다.

문제를 처음 보고 bfs 완전 탐색으로 풀 수 있을 것 같았다.
하지만 완전 탐색을 하기에는 n이 크고 이는 시간 초과 혹은 메모리초과가 날 수 있다.

따라서 다른 방법을 생각했는데 현재 좌표까지 도달하는데 든 비용을 기록하면서 이동하면 되겠다는 생각이 들었다.

현재 좌표에서 상하좌우로 이동할 때 현재 좌표까지 도달하는데 든 비용 + 이동할 좌표로 가는데 드는 비용이 이동할 좌표까지 든 비용보다 작다면 비용을 갱신해주는 방식이다.

이렇게 적고보니 다익스트라 알고리즘과 같다. 따라서 우선 순위 큐를 이용해서 풀 수가 있다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.PriorityQueue;

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] line;
        int t = 1;
        while (true) {
            n = Integer.parseInt(br.readLine());
            if (n == 0)
                break;

            map = new int[n][n];
            for (int i = 0; i < n; i++) {
                line = br.readLine().split(" ");
                map[i] = Arrays.stream(line).mapToInt(Integer::parseInt).toArray();
            }
            int[][] dist = new int[n][n];
            for (int i = 0; i < n; i++)
                Arrays.fill(dist[i], Integer.MAX_VALUE);
            dist[0][0] = map[0][0];
            PriorityQueue<Pair> priorityQueue = new PriorityQueue<>();

            priorityQueue.offer(new Pair(0, 0, map[0][0]));
            while (!priorityQueue.isEmpty()) {
                Pair p = priorityQueue.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = p.x + dx[i];
                    int ny = p.y + dy[i];
                    if ((nx >= 0 && nx < n) && (ny >= 0 && ny < n)) {
                        if(dist[nx][ny] > p.dist + map[nx][ny]) {
                            dist[nx][ny] = p.dist + map[nx][ny];
                            priorityQueue.offer(new Pair(nx, ny, dist[nx][ny]));
                        }
                    }
                }
            }
            bw.write("Problem " + t + ": " + dist[n - 1][n - 1] + "\n");
            t = t + 1;
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

class Pair implements Comparable<Pair> {
    int x;
    int y;
    int dist;

    public Pair(int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }

    @Override
    public int compareTo(Pair o) {
        return Integer.compare(this.dist, o.dist);
    }
}