1916번: 최소비용 구하기 [JAVA]

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

1916번: 최소비용 구하기

 

접근 방식) 다익스트라

1. 도착 정점과 가중치 속성을 갖는 Edge Class 생성

2. 각 정점에 대해 도착정점과 가중치 정보를 저장할 → ArrayList<Edge>[] list 생성

    시작 정점으로부터 모든 노드 간의 최단 거리를 저장할 → int[] distance 생성

    방문 여부를 체크하기 위해 → boolean[] visited 생성

    현재 갈 수 있는 노드 중에 가중치 값이 가장 작은 노드를 선택하기 위해 → PriorityQueue<Edge> pq 생성

    ⭐우선순위 큐의 정렬 기준을 정의해줘야 한다. (→ 가중치 기준 오름차순 정렬)

3. ArrayList<Edge>[] list 와  int[] distance 초기화

4. list에 연결된 정점과 가중치 값 저장해준다.

5. 입력 받은 시작 정점 설정

→ 우선순위 큐에 add하고, 해당 정점의 최단 거리 0으로 설정

6. 우선순위 큐가 빌 때까지 반복문 수행하면서 

    현재 선택된 노드에 연결된 Edge를 탐색하며, 최단거리를 업데이트해준다.

7. 결과값 → distance[도착정점] 값 출력해준다.

 

package codingTestStudy.week4;

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

public class B_1916 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());    // 도시 개수
        int M = Integer.parseInt(br.readLine());    // 버스 개수

        ArrayList<Edge>[] list = new ArrayList[N + 1];
        int[] distance = new int[N + 1];            // 최단 거리 기록
        boolean[] visited = new boolean[N + 1];     // 방문 여부
        PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> {
           // 가중치 오름차순 정렬 정의
           return e1.weight - e2.weight;
        });

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
            distance[i] = Integer.MAX_VALUE;
        }

        StringTokenizer st;
        for (int i = 0; i < M; i++) {
             st = new StringTokenizer(br.readLine());
             int start = Integer.parseInt(st.nextToken());
             int end = Integer.parseInt(st.nextToken());
             int weight = Integer.parseInt(st.nextToken());

            list[start].add(new Edge(end, weight));
        }

        st = new StringTokenizer(br.readLine());
        int startVertex = Integer.parseInt(st.nextToken());
        int endVertex = Integer.parseInt(st.nextToken());
        pq.add(new Edge(startVertex, 0));
        distance[startVertex] = 0;

        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            int nowVertex = now.endVertex;

            if (visited[nowVertex]) continue;
            visited[nowVertex] = true;
            for (int i = 0; i < list[nowVertex].size(); i++) {
                Edge temp = list[nowVertex].get(i);
                int nextVertex = temp.endVertex;
                int weight = temp.weight;

                if (distance[nextVertex] > distance[nowVertex] + weight) {
                    distance[nextVertex] = distance[nowVertex] + weight;
                    pq.add(new Edge(nextVertex, distance[nextVertex]));
                }
            }
        }
        System.out.println(distance[endVertex]);
    }
}

class Edge {
    int endVertex;
    int weight;

    public Edge(int endVertex, int weight) {
        this.endVertex = endVertex;
        this.weight = weight;
    }
}