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

문제

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

---

풀이(20분)

import java.io.*;
import java.util.*;

class Node implements Comparable<Node>{
    int x, y, weight;

    public Node(int x, int y, int weight){
        this.x = x;
        this.y = y;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}

public class Main {

    static int n;
    static int[][] arr;
    static boolean[][] visited;
    static Integer[][] count;
    static int[][] direction = new int[][]{
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
            };

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

        int problem = 1;
        while(true){
            n = Integer.parseInt(br.readLine());
            if(n == 0){
                break;
            }

            arr = new int[n][n];
            visited = new boolean[n][n];
            count = new Integer[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());
                }
            }

            dijkstra(0,0);
            
            System.out.println("Problem " + problem + ": " + count[n-1][n-1]);
            problem++;
        }

    }

    private static void dijkstra(int x, int y) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        count[x][y] = arr[x][y];
        pq.add(new Node(x, y, 0));


        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (visited[cur.x][cur.y])
                continue;
            visited[cur.x][cur.y] = true;

            for (int i = 0; i < 4; i++) {
                int nextX = cur.x + direction[i][0];
                int nextY = cur.y + direction[i][1];
                if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n)
                    continue;
                if (count[nextX][nextY] == null) {
                    count[nextX][nextY] = count[cur.x][cur.y] + arr[nextX][nextY];
                    pq.add(new Node(nextX, nextY, count[nextX][nextY]));
                }
            }
        }
    }
}

 

다익스트라 알고리즘을 이용한 간단한 문제이다. 다익스트라를 모른다면 https://to-travel-coding.tistory.com/267 블로그를 참고하자.

 

우선 다익스트라를 사용해야 한다는 결론을 어떻게 내린 걸까?

1. 가중치가 최단이 되게 움직여야 한다. -> 최단 거리 이동과 유사하다.

2. 음의 가중치가 존재하지 않는다. -> 다익스트라 알고리즘을 사용할 수 있다.

 

따라서 (0,0)이라는 출발점에 대해 다익스트라 알고리즘을 적용하여 문제를 어렵지 않게 해결할 수 있었다.