[BaekJoon] 1916번 최소비용 구하기 (Java) 문제 풀이 [Gold 5]

문제

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

1916번: 최소비용 구하기

 

어떻게 풀 것인가?

문제의 제목부터가 "최소비용 구하기" 이다. 

그래서 다익스트라 최단경로 구하는 알고리즘을 사용하였다.

사실 그래서 처음 접근 자체는 크게 어렵지 않았다.

내 코드의 핵심은 "우선순위 큐를 활용한 다익스트라 최단 경로 탐색" 이라고 볼 수있다.

 

우선순위 큐를 사용하는 다익스트라 알고리즘의 시간 복잡도는 O((V + E) log V) 이다. PriorityQueue로 인해 O(log V) 연산을 하므로 효율적이다.

• 그래프 입력 방식: 인접 리스트 ArrayList<Node>[] 사용
• 우선순위 큐 (PriorityQueue) 를 사용하여 최소 비용부터 탐색
• 시간 복잡도 O((V + E) log V) 로 최적화
• 출력 시 최단 거리 dist[end] 출력

 

풀면서 놓쳤던점

X

 

이 문제를 통해 얻어갈 것

다익스트라 알고리즘

 

내 코드 

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

// 백준알고리즘 1916번 최소비용 구하기

public class Main {
    static int N, M;
    static int start, end;
    static ArrayList<Node>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        graph = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[v].add(new Node(w, cost));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        Dijkstra();
    }

    public static void Dijkstra() {
        boolean[] check = new boolean[N + 1];
        int[] dist = new int[N + 1];
        int INF = Integer.MAX_VALUE;

        Arrays.fill(dist, INF);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            int nowVertex = pq.poll().index;

            if (check[nowVertex]) continue;
            check[nowVertex] = true;

            //index의 연결된 정점 비교
            for (Node next : graph[nowVertex]) {
                if (dist[next.index] > dist[nowVertex] + next.cost) {
                    dist[next.index] = dist[nowVertex] + next.cost;

                    pq.offer(new Node(next.index, dist[next.index]));
                }
            }
        }

        System.out.print(dist[end]);

    }
}

class Node implements Comparable<Node> {
    int index;
    int cost;

    public Node(int index, int cost) {
        this.index = index;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.cost, o.cost);
    }
}

 

참고

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘/Java]다익스트라(Dijkstra) 알고리즘