[백준 1916] 최소비용 구하기(JAVA)

백준 1916번 문제 - 최소비용 구하기

1916번: 최소비용 구하기

---

문제 분석 

 

 

• N개의 도시가 있다.
  • 도시의 번호는 1부터 N까지이다.
• 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다.
• 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.
• A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라.

---

해결 포인트

•  

 

• 다익스트라(Dijkstra) 알고리즘 사용
• 버스 클래스 구현
  • 버스 도착지
  • 버스 비용
• 버스 Comparable는 비용이 작은 순으로 정렬되도록 구현
• 우선순위 큐 사용  
  •  Queue<Bus> queue = new PriorityQueue<>(); 
• 시작지부터 N개의 도시까지 최소비용을 저장할 배열(dp) 구현
• 방문 확인 visited 배열 구현
• 처음 시작지 큐에 삽입 및 dp 저장 
  •  queue.add(new Bus(sCity, 0)); 
  • dp[sCity] = 0; 
• 큐가 빌 때까지 반복
  • 큐에서 하나 꺼내기
  • 방문한 도시면 패스(continue)
  • 방문 안한 도시면 방문 등록 후, 해당 도시에서 갈 수 있는 버스노선 확인
    • 해당 버스 탔을 때, dp[도착지]가 현재 cost + dp[현재도시] 보다 클 경우(dp[b.e] >= dp[start] + b.cost)
    • dp 변환 및 큐에 삽입

---

코드

 

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

public class Main {
    public static int N,M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        ArrayList<Bus> [] busList = new ArrayList[N+1];

        for (int i = 1; i <= N; i++) {
            busList[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            busList[start].add(new Bus(end, cost));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());

        int city1 = Integer.parseInt(st.nextToken());
        int city2 = Integer.parseInt(st.nextToken());

        bw.write(Dijkstra(city1, city2, busList) + "\n");

        bw.flush();
        bw.close();
    }

    public static long Dijkstra(int sCity, int eCity, ArrayList<Bus> [] busList) {
        Queue<Bus> queue = new PriorityQueue<>();
        boolean [] visited = new boolean[N+1];
        int [] dp = new int[N+1];

        Arrays.fill(dp, Integer.MAX_VALUE);

        queue.add(new Bus(sCity, 0));
        dp[sCity] = 0;

        while (!queue.isEmpty()) {
            Bus value = queue.poll();
            int start = value.e;

            if(visited[start]) continue;

            visited[start] = true;
            for (Bus b : busList[start]) {
                if(dp[b.e] >= dp[start] + b.cost) {
                    dp[b.e] = dp[start] + b.cost;
                    queue.add(new Bus(b.e, dp[b.e]));
                }
            }
        }

        return dp[eCity];
    }

    public static class Bus implements Comparable<Bus> {
        int e;
        int cost;

        public Bus(int end, int cost) {
            e = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Bus o) {
            return cost - o.cost;
        }
    }
}