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

 

문제 분석

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

전형적인 bfs문제다.

보드가 주어지고 0,0에서 n-1,n-1로의 경로 중 가장 저렴한 비용으로 갈 때 그 비용을 묻는 문제였다.

 

point마다 해당 point까지 온 cost를 저장하고 이를 PQ에 낮은 순으로 삽입한다.

또, point에 방문했을 때 굳이 더 비싼 비용으로 도착한 경우 탐색을 이어나갈 필요가 없기에 이 부분도 같이 체크해주면 된다.

 

코드

import java.util.*;

public class Main {


    public static void main(String[] args) throws InterruptedException {
        Scanner sc = new Scanner(System.in);
        int testNum = 1;
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        while (true){
            int n = sc.nextInt();
            if(n == 0)
                break;

            int[][] cost = new int[n][n];
            int[][] board = new int [n][n];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    board[i][j] = sc.nextInt();
                    cost[i][j] = Integer.MAX_VALUE;
                }
            }

            PriorityQueue<Point> pq =new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));

            pq.add(new Point(0,0,0));
            int ans = board[0][0];

            while (!pq.isEmpty()){
                Point poll = pq.poll();
                if(cost[poll.x][poll.y] <= poll.cost)
                    continue;
                cost[poll.x][poll.y] = poll.cost;

                if(poll.x == n-1 && poll.y == n-1){
                    ans += poll.cost;
                    break;
                }


                for (int i = 0; i < 4; i++) {
                    int nx = poll.x + dx[i];
                    int ny = poll.y + dy[i];
                    if(nx >=0 && ny >=0 && nx < n && ny <n && cost[nx][ny] > poll.cost + board[nx][ny]){
                        pq.add(new Point(nx,ny,poll.cost + board[nx][ny]));
                    }
                }

            }

            System.out.println("Problem "+testNum+": "+ans);






            testNum++;
        }
    }

    static class Point{
        int x,y,cost;

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



}