[JAVA] 백준 1916 다익스트라

 

 

 

 

1916번: 최소비용 구하기

문제

도시들이 주어지고 도시들을 연결해주는 버스가 주어졌을 때 출발지 도시에서 목적지 도시까지의 최단 거리를 구하여라.

풀이

최적화된 다익스트라 알고리즘 설명

[JAVA] 백준 1753 다익스트라

음의 가중치가 없었기 때문에 다익스트라 알고리즘을 사용하여 문제를 해결하였습니다.

📌 입력

      ArrayList<Bus>[] A = new ArrayList[N];
      boolean[] V = new boolean[N];
      int[] distance = new int[N];
      for(int i=1; i<N; i++){
          A[i] = new ArrayList<>();
          distance[i] = INF;
      }

      StringTokenizer st;
      for(int i=0; i<M; i++){
          st = new StringTokenizer(br.readLine(), " ");
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          int w = Integer.parseInt(st.nextToken());

          A[a].add(new Bus(b, w));
      }
    static class Bus{
        int destination;
        int weight;
        Bus(int destination, int weight){
            this.destination = destination;
            this.weight = weight;
        }
    }

Bus 클래스를 만들어서 버스의 목적지와 가중치를 담았습니다.

A : 연결 리스트 형태로 만든 그래프

distance : 현재의 최단 거리 배열

V : 방문한 정점을 체크

📌 다익스트라 알고리즘

      PriorityQueue<Bus> q = new PriorityQueue<>((o1, o2) -> {
          return o1.weight - o2.weight;
      });
      q.add(new Bus(S, 0));
      distance[S] = 0;
      while (!q.isEmpty()){
          Bus now = q.poll();
          if(V[now.destination]) continue;
          V[now.destination] = true;

          for(Bus x : A[now.destination]){
              if(distance[x.destination] > distance[now.destination] + x.weight){
                  distance[x.destination] = distance[now.destination] + x.weight;
                  q.add(new Bus(x.destination, distance[x.destination]));
              }
          }
      }

우선순위 큐를 사용하여 다익스트라 알고리즘을 구현하였습니다. (최적화된 다익스트라 알고리즘에 대한 설명은 위에 링크를 참고해주세요)

출발 도시 S부터 다른 모든 정점까지의 최단 거리를 구했습니다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      int N = Integer.parseInt(br.readLine())+1;
      int M = Integer.parseInt(br.readLine());

      ArrayList<Bus>[] A = new ArrayList[N];
      boolean[] V = new boolean[N];
      int[] distance = new int[N];
      for(int i=1; i<N; i++){
          A[i] = new ArrayList<>();
          distance[i] = INF;
      }

      StringTokenizer st;
      for(int i=0; i<M; i++){
          st = new StringTokenizer(br.readLine(), " ");
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          int w = Integer.parseInt(st.nextToken());

          A[a].add(new Bus(b, w));
      }
      st = new StringTokenizer(br.readLine(), " ");
      int S = Integer.parseInt(st.nextToken());
      int D = Integer.parseInt(st.nextToken());

      PriorityQueue<Bus> q = new PriorityQueue<>((o1, o2) -> {
          return o1.weight - o2.weight;
      });
      q.add(new Bus(S, 0));
      distance[S] = 0;
      while (!q.isEmpty()){
          Bus now = q.poll();
          if(V[now.destination]) continue;
          V[now.destination] = true;

          for(Bus x : A[now.destination]){
              if(distance[x.destination] > distance[now.destination] + x.weight){
                  distance[x.destination] = distance[now.destination] + x.weight;
                  q.add(new Bus(x.destination, distance[x.destination]));
              }
          }
      }
        System.out.println(distance[D]);

    }

    static class Bus{
        int destination;
        int weight;
        Bus(int destination, int weight){
            this.destination = destination;
            this.weight = weight;
        }
    }
}

결과