BOJ) 녹색 옷 입은 애가 젤다지? (4485 번)

녹색 옷 입은 애가 젤다지?

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

 

다익스트라를 알고, 적절하게 이용할 줄 아는가?를 물어보는 문제였다.

좌측 상단에서 우측 하단으로 이동하면서 돈을 가장 적게 뺏겨야하는 문제다.

처음에는 dp로 간단하게 풀 수 있겠다고 생각하고 코드를 작성했지만, 불규칙적으로 왔다갔다하는 경우가 있어서 다익스트라를 추가해줬다.

출발 지점을 우선순위 큐에 담아두고, 상하좌우를 돌면서 돈을 가장 적게 뺏기는 경우들을 저장하면서 큐에 넣어주었다.

이동하면서, 가장 적게 뺏기는 경우들로 dp가 채워지고 도착했을 때 저장된 값을 출력해주면되는 문제였다.

 

코드

 

package remindBOJ;

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

public class Zelda_4485 {
    final static String PREFIX ="Problem ", COLON =": ", NEW_LINE ="\n";
    final static int END = 0;
    final static int[] dx = {0,0,1,-1}, dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n =0;
        int count =1;
        while( (n = Integer.parseInt(br.readLine())) !=END ) {
            int[][] map = new int[n][n];
            for(int i=0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j=0; j<n; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            sb.append(PREFIX).append(count++).append(COLON).append(dijkstra(map,n)).append(NEW_LINE);
        }
        br.close();
        System.out.println(sb.toString());
    }
    private static int dijkstra(int[][] map, int n) {
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = map[0][0];
        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.offer(new Pos(0,0,map[0][0]));

        while(!pq.isEmpty()) {
            Pos pos = pq.poll();

            for(int i=0; i<4; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];
                if(isInArea(nx,ny,n)) {
                    if(dp[ny][nx] > dp[pos.y][pos.x] + map[ny][nx]) {
                        dp[ny][nx] = dp[pos.y][pos.x] + map[ny][nx];
                        pq.offer(new Pos(nx,ny, dp[ny][nx]));
                    }
                }
            }
        }
        return dp[n-1][n-1];
    }

    private static boolean isInArea(int x, int y, int n) {
        return x>=0 && y>=0 && x<n && y<n;
    }

    private static class Pos implements Comparable<Pos>{
        int x, y, cost;
        public Pos(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }

        @Override
        public int compareTo(Pos pos) {
            return this.cost - pos.cost;
        }
    }
}