[백준] 4485번 - 녹색 옷 입은 애가 젤다지? - 자바(JAVA)

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

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

 

문제 해석

젤다의 전설 게임의 화폐 단위는 루피이다.

'도둑 루피'라 불리는 검은색 루피도 존재하여 이것을 획득하면 오히려 소지한 루피가 감소됩니다.

현재 주인공 '링크'는 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있습니다. 

즉, 시작점은 (0,0)에 위치

 

링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 합니다.

이동은 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다.

 

각 칸마다 도둑루피가 존재하는데 이 칸을 지나면 해당 도둑 루피의 크기만큼 소지금을 잃게 됩니다.

이때 잃을 수 있는 금액의 최솟값은 얼마일까요?

 

 

문제 풀이 전 설계

우선 가장 간단한 접근으로 오른쪽,아래로만 이동하면서 모든 경우를 탐색해 보겠습니다.

반례가 생각났습니다.

 

만약 다음과 같이 움직인다면 왼쪽으로도 이동해주어야 합니다.

비슷한 예시로 위쪽으로 이동해야하는 경우도 있을 수 있습니다.

I,INF는 무한대를 의미합니다.

 

따라서 BFS와DP, 우선순위 큐를 결합하여 해당 좌표까지 잃은 소지금을 PQ에 넣어 소지금이 적은 순으로 이동합니다.

또한 이동하려고 하는 곳이 이미 계산되어 있으며 현재 값보다 작다면 이동하지 않습니다.

 

즉, 다익스트라 알고리즘을 적용하면 됩니다.

 

코드

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

public class Main_4485_녹색옷입은애가젤다지 {

    static int size;
    static int[][] board,dp;

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

    static class Pos{
        int y;
        int x;
        int cost;

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

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;
        int tc = 1;

        while ((size = Integer.parseInt(br.readLine())) != 0) {

            board = new int[size][size];
            dp = new int[size][size];

            for (int y = 0 ; y < size; y++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int x = 0; x < size; x++) {
                    board[y][x] = Integer.parseInt(st.nextToken());
                    dp[y][x] = Integer.MAX_VALUE; //dp 배열에 최댓값으로 채워놓음
                }
            }

            PriorityQueue<Pos> pq = new PriorityQueue<>( (e1,e2) -> e1.cost - e2.cost);
            pq.add(new Pos(0,0,board[0][0]));
            dp[0][0] = board[0][0];

            while(!pq.isEmpty()){
                Pos curPos = pq.poll();
                for(int k=0;k<4; k++){
                    int tempY = curPos.y + dy[k];
                    int tempX = curPos.x + dx[k];

                    if(!visited(tempY,tempX)){
                        continue;
                    }

                    if(dp[tempY][tempX] > dp[curPos.y][curPos.x] + board[tempY][tempX]){
                        dp[tempY][tempX] = dp[curPos.y][curPos.x] + board[tempY][tempX];
                        pq.add(new Pos(tempY,tempX, dp[tempY][tempX]));
                    }
                }
            }

            sb.append("Problem "+ tc++ + ": " + dp[size-1][size-1] + "\n");
        }
        System.out.println(sb.toString());

    }

    private static boolean visited(int tempY, int tempX) {
        return tempY < size && tempX < size && tempY >= 0 && tempX >=0;
    }


}