[BOJ/Dijkstra] 백준 4485 - 녹색 옷을 입은 애가 젤다지? (Java)

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

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

문제

도둑루피(검정색 루피): 소지한 루피 감소
도둑루피만 가득한 N*N 크기의 동굴의 제일 왼쪽 위 [0][0]에 잇음
동굴의 반대편 출구인 제일 오른쪽 아래 칸 [N-1][N-1]까지 이동해야 함/ 상하좌우 1칸 식 이동 가능
각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피 크기만큼 소지금 잃음
=> 잃을 수밖에 없는 최소 금액?

입력: 여러 개의 테스트 케이스로 이뤄짐
각 테스트 케이스 첫째 줄: 동굴의 크기 나타내는 정수 N (2 <= N <= 125) / N = 0 -> 전체 입력 종료
N개 줄: 동굴의 각 칸에 있는 도둑루피의 크기 (IF. 크기 k -> 이 칸 지나면 k루피 잃음) (0 <= k <= 9)
출력: 각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰 출력

---

풀이

각 칸에 적힌 비용(루피) 최소로 하면서 (0, 0) -> (N-1, N-1)까지 이동 = 최단 경로 문제

 

Node 클래스

(x, y)까지 도달하는 데 드는 비용

static class Node implements Comparable<Node> {
    int x, y, cost;

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

    @Override
    public int compareTo(Node o) {
        return this.cost - o.cost;
    }
}

 

• `map`: 입력으로 주어진 루피 비용 지도
• `dist`: (0, 0) -> (i, j)까지 오는데 걸리는 최소 비용

 

• `pQ.offer(new Nodw(0, 0, map[0][0]))`: 시작점 (0, 0) 비용은 자기 자신 비용

static int dijkstra() {
    PriorityQueue<Node> pQ = new PriorityQueue<>();
    dist[0][0] = map[0][0];
    pQ.offer(new Node(0, 0, map[0][0]));

    while (!pQ.isEmpty()) {
        Node cur = pQ.poll();

        if (cur.cost > dist[cur.x][cur.y]) continue;

        for (int d = 0; d < 4; d++) {
            int nx = cur.x + dx[d];
            int ny = cur.y + dy[d];

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

            int nextCost = cur.cost + map[nx][ny];
            if (nextCost < dist[nx][ny]) {
                dist[nx][ny] = nextCost;
                pQ.offer(new Node(nx, ny, nextCost));
            }
        }
    }

    return dist[N - 1][N - 1];
}

---

코드

import java.io.*;
import java.util.*;

// 녹색 옷을 입은 애가 젤다지?
public class boj_4485 {
    static class Node implements Comparable<Node> {
        int x, y, cost;

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

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }

    static int N;
    static int[][] map, dist;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static final int INF = Integer.MAX_VALUE;

    static int dijkstra() {
        PriorityQueue<Node> pQ = new PriorityQueue<>();
        dist[0][0] = map[0][0];
        pQ.offer(new Node(0, 0, map[0][0]));

        while (!pQ.isEmpty()) {
            Node cur = pQ.poll();

            if (cur.cost > dist[cur.x][cur.y]) continue;

            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

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

                int nextCost = cur.cost + map[nx][ny];
                if (nextCost < dist[nx][ny]) {
                    dist[nx][ny] = nextCost;
                    pQ.offer(new Node(nx, ny, nextCost));
                }
            }
        }

        return dist[N - 1][N - 1];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int cnt = 1;

        while (true) {
            N = Integer.parseInt(br.readLine());
            if (N == 0) break;

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

            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());
                }
            }

            sb.append("Problem ").append(cnt++).append(": ").append(dijkstra()).append("\n");
        }

        System.out.println(sb);
    }
}