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

 

Priority Queue를 활용한 BFS => 다익스트라 방식으로 풀었다.

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

class Point {
    int x;
    int y;
    int val;

    public Point(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

public class Solution {

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int solution(int N, int[][] arr) {
        int answer = 0;
        PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return o1.val - o2.val;
            }
        });

        boolean[][] chk = new boolean[N][N];
        pq.offer(new Point(0, 0, arr[0][0]));
        chk[0][0] = true;

        while(!pq.isEmpty()) {
            Point tmp = pq.poll();

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

                if(nx == N-1 && ny == N-1) {
                    answer = tmp.val + arr[nx][ny];
                    return answer;
                }

                if(nx >=0 && nx <N && ny>=0 && ny < N && !chk[nx][ny]) {
                    chk[nx][ny] = true;
                    pq.offer(new Point(nx, ny, tmp.val + arr[nx][ny]));
                }
            }
        }
        return answer;
    }

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

        int N;
        int count = 1;
        int sol;

        while(true) {
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            if(N == 0) {
                break;
            }
            int[][] arr = new int[N][N];
            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for(int j=0; j<N; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            sol = solution(N, arr);
            sb.append("Problem ").append(count).append(": ").append(sol).append("\n");
            count ++;
        }
        System.out.println(sb.toString());
    }
}