[백준] 4485번 - 녹색 옷 입은 애가 젤다지? JAVA 풀이

문제

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

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

문제 유형

다익스트라(dijkstra)

 

문제 풀이

추가예정

 

전체코드

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

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

    public Node(int y, int x, int distance){
        this.x= x;
        this.y= y;
        this.distance = distance;
    }
    @Override
    public int compareTo(Node other) {
        if (this.distance < other.distance) {
            return -1;
        }
        return 1;
    }
}
public class Main {
    static int N;
    static int[][] map;
    static int[][] d;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

    static final int INF = 1000000000;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            count++;
            N = Integer.parseInt(br.readLine());
            if(N==0){
                break;
            }
            map = new int[N][N];
            d = new int[N][N];

            for (int i = 0; i < N; i++) {
                String[] input = br.readLine().split(" ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(input[j]);
                    d[i][j] = INF;
                }
            }
            dijkstra();
            //d_print();
            System.out.println("Problem "+count+": "+d[N-1][N-1]);
        }
    }


    private static void d_print() {
        for(int i=0; i<N; i++){
            Arrays.stream(d[i]).forEach(j-> System.out.print(j+" "));
            System.out.println();
        }
    }

    public static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(0,0,map[0][0])); //start x,y
        d[0][0] = map[0][0]; //start d[y][x]

        while (!pq.isEmpty()) {

            Node node = pq.poll();
            for (int i = 0; i < dx.length; i++) {
                int next_x = node.x + dx[i];
                int next_y = node.y + dy[i];
                if (next_x >= N || next_y >= N || next_y < 0 || next_x < 0) {
                    continue;
                }
                if(d[node.y][node.x] < node.distance){ continue; }
                int cost = map[next_y][next_x] + d[node.y][node.x];

                if (cost < d[next_y][next_x]) {
                    d[next_y][next_x] = cost;
                    pq.offer(new Node(next_y, next_x, map[next_y][next_x]));

                }
            }
        }
    }
}