백준 4485번 : 녹색 옷 입은 애가 젤다지? java

이 문제는 다익스트라 알고리즘을 이용하여 (0, 0)에서 (N-1, N-1)까지 갈 때까지 최소한으로 소지금을 잃으면 서 갈 수 있는 경로를 찾는 문제입니다.

우선 (0, 0)에서 시작하여 주변 정점들의 비용을 확인하면서 더 비용이 적게 드는 경로를 선택하여 진행하면 됩니다.

---

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

public class Main {
    static int[] dR = {1, -1, 0, 0};
    static int[] dC = {0, 0, 1, -1};

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

        while(true){
            int N = Integer.parseInt(br.readLine());
            cnt++;

            if(N == 0)
                break;

            int[][] cave = new int[N][N];
            int[][] thiefLoopy = new int[N][N];

            //cave와 thiefLoopy 초기화
            for(int i = 0; i<N; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());

                for(int j = 0; j<N; j++) {
                    cave[i][j] = Integer.parseInt(st.nextToken());
                    thiefLoopy[i][j] = -1;
                }
            }

            Queue<Node> q = new PriorityQueue<>();
            q.offer(new Node(0, 0, cave[0][0]));
            thiefLoopy[0][0] = cave[0][0];

            while(!q.isEmpty()){
                Node a = q.poll();

                if(a.row == N-1 && a.col == N-1){
                    sb.append("Problem ").append(cnt).append(": ").append(a.loopy).append("\n");
                    break;
                }

                for(int i = 0; i<4; i++){
                    int dr = a.row + dR[i];
                    int dc = a.col + dC[i];

                    if(dr<0||dc<0||dr>=N||dc>=N)
                        continue;
                    if(thiefLoopy[dr][dc] >= a.loopy + cave[dr][dc])
                        continue;

                    thiefLoopy[dr][dc] = a.loopy + cave[dr][dc];
                    q.offer(new Node(dr, dc, thiefLoopy[dr][dc]));
                }
            }
        }

        System.out.print(sb);
    }
}
class Node implements Comparable<Node>{
    int row, col, loopy;

    Node(int row, int col, int loopy){
        this.row = row;
        this.col = col;
        this.loopy = loopy;
    }

    @Override
    public int compareTo(Node a){
        return this.loopy - a.loopy;
    }
}