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

다익스트라를 활용하는 최단거리 문제이다.

문제를 맨처음 보았을 때 단순하게 백트래킹으로 모든 경로를 확인해보았다. 하지만 주어질 수 있는 동굴의 크기의 최대값이 125이기 때문에 시간초과가 발생하게 된다. 따라서 다익스트라를 활용해보았다. 다익스트라는 기본적으로 다음과 같은 원리로 동작한다.

1. 출발 노드를 설정
2. 최단 거리 테이블을 최대값으로 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 위 과정에서 3번 4번을 반복

그래프와 다르게 2차원 배열에서는 4방향을 갈수있다고 가정하고, 우선순위 큐를 이용하여 구현해보았다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_bj_1916_최소비용구하기 {
    static class Edge implements Comparable<Edge> {
        int point, weight;
 
        public Edge(int point, int weight) {
            this.point = point;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(weight, o.weight);
        }
    }
 
    static int N, M;
    static List<Edge>[] edgeList;
    static int[] d;
    static boolean[] visit;
    static PriorityQueue<Edge> pq;
    static int start, end;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
 
        pq = new PriorityQueue<>();
        d = new int[N + 1];
        visit = new boolean[N + 1];
        edgeList = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            d[i] = Integer.MAX_VALUE / 2;
            edgeList[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
 
            edgeList[u].add(new Edge(v, w));
        }
 
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
 
        dijkstra(start);
 
        System.out.println(d[end]);
    }
 
    static void dijkstra(int begin) {
        d[start] = 0;
        visit[start] = true;
        pq.add(new Edge(begin, 0));
 
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int startPoint = cur.point;
 
            for (Edge edge : edgeList[startPoint]) {
                int endPoint = edge.point;
 
                if (visit[endPoint] == false && d[endPoint] > d[startPoint] + edge.weight) {
                    d[endPoint] = d[startPoint] + edge.weight;
                    pq.add(new Edge(endPoint, d[endPoint]));
                }
            }
 
            visit[startPoint] = true;
        }
    }
}