Baekjoon | Q.1753 - 최단경로

 

1753번: 최단경로

다익스트라 알고리즘을 이용하여 가중 그래프에서 출발 정점으로부터 각 정점의 최단 경로를 구하는 문제이다.

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  static class Graph implements Comparable<Graph> {
    int vertex;
    int weight;

    public Graph(int vertex, int weight) {
      this.vertex = vertex;
      this.weight = weight;
    }

    @Override
    public int compareTo(Graph target) {
      if(this.weight > target.weight) {
        return 1;
      }else if(this.weight < target.weight) {
        return -1;
      }
      return 0;
    }

  }
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int V = sc.nextInt();
    int E = sc.nextInt();
    int start = sc.nextInt();

    ArrayList<Graph>[] li = new ArrayList[V+1];
    PriorityQueue<Graph> pq = new PriorityQueue<>();
    int[] distance = new int[V+1];  // 거리 저장
    
    // 초기화
    for (int i = 1; i < distance.length; i++) {
      li[i] = new ArrayList<>();
      distance[i] = Integer.MAX_VALUE;
    }
	
    // 간선 정보 입력
    for (int i = 0; i < E; i++) {
      int from = sc.nextInt();
      int to = sc.nextInt();
      int w = sc.nextInt();

      li[from].add(new Graph(to, w));
    }

    sc.close();
    
    // 다익스트라 알고리즘 시작
    distance[start] = 0;  // 시작정점 거리 0
    pq.add(new Graph(start, 0));  // 큐에 추가

    while(!pq.isEmpty()) { // 큐에 대기열이 없을 때까지 반복
      Graph now = pq.poll();	// 가장 짧은 거리를 가진 정점부터 대기열에서 꺼내서 탐색시작

      for (Graph next : li[now.vertex]) { // 연결된 정점 탐색
        int d = distance[now.vertex] + next.weight;	// 새로운 경로의 거리
        if(distance[next.vertex] > d) {	// 새로운 경로가 이전의 경로보다 거리가 짧다면
          distance[next.vertex] = d;	// 최단경로 갱신
          pq.add(new Graph(next.vertex, d));	// 다음 정점은 대기열에 추가
        }
      }
    }
    
    // 출력
    for (int i = 1; i < distance.length; i++) {
      if(distance[i] == Integer.MAX_VALUE) System.out.println("INF");
      else System.out.println(distance[i]);
    }
  }
}

 처음에 그래프를 인접행렬로 구현했더니 메모리초과가 되었다.. 그래서 인접 리스트로 다시 그래프를 구현하였다.

최단 경로를 찾기 위해 다익스트라 알고리즘은 가장 짧은 거리를 가진 정점부터 방문을 시작한다. for문으로 가장 짧은 거리를 가진 정점을 탐색해도 되지만 우선순위 큐를 이용한다면 더욱 효율적인 코드를 만들 수 있다.