[BOJ] 4485번 녹색 옷 입은 애가 젤다지? - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {

    static class Pos implements Comparable<Pos> {
        int r;
        int c;
        int cost;

        public Pos(int r, int c, int cost) {
            super();
            this.r = r;
            this.c = c;
            this.cost = cost;
        }

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

    }

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    static final int INF = (int) 1e9;

    static int N;
    static int[][] map, cost;
    static boolean[][] used;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder result = new StringBuilder();
        int tc = 1;
        while (true) {
            N = Integer.parseInt(br.readLine());
            if (N == 0) break;
            init(br);
            dijkstra(new Pos(0, 0, map[0][0]));
            setResult(result, tc++);
        }
        print(result);
    }

    private static void init(BufferedReader br) throws IOException {
        map = new int[N][N];
        cost = new int[N][N];
        used = new boolean[N][N];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        initCost();
    }

    private static void initCost() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(cost[i], INF);
        }
    }

    private static void dijkstra(Pos start) {
        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.add(start);
        cost[0][0] = map[0][0];
        while (!pq.isEmpty()) {
            Pos now = pq.poll();
            int r = now.r;
            int c = now.c;
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (isOutOfRange(nr, nc))
                    continue;
                int next = cost[r][c] + map[nr][nc];
                if (cost[nr][nc] > next) {
                    cost[nr][nc] = next;
                    pq.add(new Pos(nr, nc, cost[nr][nc]));
                }
            }
        }
    }

    private static boolean isOutOfRange(int nr, int nc) {
        return nr < 0 || nc < 0 || nr >= N || nc >= N;
    }

    private static void setResult(StringBuilder result, int tc) {
        result.append("Problem ");
        result.append(tc);
        result.append(": ");
        result.append(cost[N - 1][N - 1]);
        result.append("\n");
    }

    private static void print(StringBuilder result) {
        System.out.println(result);
    }
}

📄 해설

• 우선순위 큐를 이용한 다익스트라 알고리즘을 적용하면 쉽게 풀리는 문제
• 2차원 최소비용 배열 cost 는 INF 로 초기화하고, 다익스트라 알고리즘을 수행
• 이때 최소비용의 갱신은 현재까지의 최소 비용 + 다음칸의 비용 과 현재 저장되어있는 다음칸의 최소비용 을 비교하여 갱신함