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

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

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

 

다익스트라 알고리즘 문제라고 한다. PrioPriorityQueue를 이용해서 각 좌표의 최단 거리를 탐색한다.

+) 다익스트라 문제는 Dynamic 프로그래밍 처럼 작은것이 모여서 큰것이 될 수 도 있고, 정렬을 사용하게 되면 Greedy 처럼 해결할 수 도 있다. 

PriorityQueue에 조건만 잘 주면 된다!

ps. 다음부터 큐에 좌표값 넣을 때 클래스 만들자 .. 코드가 더러운거같다.ㅠㅠ;

  + 쿠팡 온라인 테스트에 비슷한 문제가 제출되어서 풀어봤다 ...;;

import java.io.*;
import java.util.*;
 
public class Main_젤다 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int[] di = { 0, 1, 0, -1 }, dj = { 1, 0, -1, 0 };
        int tc = 0;// 테스트케이스
        while (true) {
            tc++;
            int n = Integer.parseInt(br.readLine());
            if (n == 0)
                break;
 
            int[][] map = new int[n][n]; // 입력 맵
            int[][] tmap = new int[n][n]; // 최소값 넣는 맵
            int INF = Integer.MAX_VALUE;
            boolean[][] visit = new boolean[n][n];
            PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
 
                @Override
                public int compare(int[] o1, int[] o2) {
                    return Integer.compare(o1[2], o2[2]);
                }
            });
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    tmap[i][j] = INF;
                }
            }
            tmap[0][0] = map[0][0]; // 스타트 지점은 항상 최소값이다
            q.add(new int[] { 0, 0, map[0][0] });
            while (!q.isEmpty()) {
                int[] arr = q.poll();
                int x = arr[0];
                int y = arr[1];
                int w = arr[2];
                
                if (x == n - 1 && y == n - 1) {
                    System.out.println("Problem " + tc + ":" + " " + w);
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = x + di[i];
                    int ny = y + dj[i];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < n &&!visit[nx][ny] && 
                            tmap[nx][ny] > tmap[x][y] + map[nx][ny]) {
                        tmap[nx][ny] = tmap[x][y] + map[nx][ny];
                        q.add(new int[] { nx, ny, tmap[nx][ny] }); 
                    }
                }
                visit[x][y] = true;
 
            }
 
        }
    }
 
}

+ 코드설명

line 28 ~ 33 : cost 값을 셋팅해 줘야 합니다.  최솟값으로 최댓값으로, 최댓값이라면 최솟값으로 =

line 35 : 시작 하는 지점을 map[0][0] 으로 지정해야 합니다. 

line 51 : 이전에 가봤거나 혹은 최댓값인 경우(초기 셋팅된 값으로) 와 현재 cost 비용 그리고 다음 위치의 맵 값과 반드시 비교해줘야 합니다.