최단경로 [JAVA] (백준 1753)

 

문제

문제 링크 : https://www.acmicpc.net/problem/1753

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	256MB	84967	22765	10970	23.492%

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

풀이

우선 그래프를 $V \times V$로 만들면 int만 4억개가 되어버리므로 메모리가 폭파해버린다.

따라서 연결 리스트 형식으로 구현해야 한다.

나는 처음에 V개의 배열 원소에 각각 노드마다 다음 노드를 키로, 무게를 값으로 하는 해시맵을 사용한 뒤 다익스트라 알고리즘을 구현하였다.

하지만 이렇게 구현할 경우에는 시간복잡도가 $O(EV)$가 나와버려 시간초과를 당하게 된다.

 

해답은 우선순위 큐를 사용해야 한다.

우선 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은(비교에서 음수) 데이터가 먼저 나오는 큐이다.

힙을 사용하여 구현하는데, 중복을 허용하지 않는다.

우선순위 큐를 사용하게 된다면, 방문가능한 원소들 중 최소값을 먼저 방문하게 되어 최악의 경우를 걸러주게 된다. $O((V+E)logV)$

하지만 우선순위 큐를 사용하기 위해서는 방문할 다음 정점과 함께 - 그 정점을 방문했을때의 값의 상황을 함께 가지고 있어야 거리 상황에 따라 우선순위 큐가 작동하게 된다.

따라서 Pair라는 클래스를 선언하고, Compareable 인터페이스를 상속하게 하여 각각의 Pair끼리 값을 비교하여 우선순위를 정하도록 해주었다.

Integer.compare(A, B)를 사용하여 A가 더 크면 양수, B가 더 크면 음수, 같으면 0에 따라 우선순위큐가 알아서 잘 비교해서 작동하도록 하였다.

 

코드

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 Main {
    static int V;
    static int E;
    static int start;

    static int MAX = 9999999;

    static ArrayList<ArrayList<Pair>> Vmap;
    static int[] answer;

   public static void main(String[] args) throws IOException{
      StringTokenizer st;
      BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));

      st = new StringTokenizer(br.readLine());
      V = Integer.parseInt(st.nextToken());
      E = Integer.parseInt(st.nextToken());
      //시작 정점의 번호
      start = Integer.parseInt(br.readLine())-1;

      //2차원 배열 -> 32억바이트
      Vmap = new ArrayList<ArrayList<Pair>>();
      answer = new int[V];

      for(int i=0; i<V; i++) {
          Vmap.add(new ArrayList<Pair>());
          answer[i] = MAX;
      }
      //자기 자신은 0
      answer[start] = 0;



      for(int i=0; i<E; i++) {
          st = new StringTokenizer(br.readLine());
          int x = Integer.parseInt(st.nextToken()) -1;
          int y = Integer.parseInt(st.nextToken()) -1;
          int val = Integer.parseInt(st.nextToken());

          Vmap.get(x).add(new Pair(y, val));
      }

      PriorityQueue<Pair> queue = new PriorityQueue<Pair>();
      int[] check = new int[V];

      queue.add(new Pair(start,0));

      while(!queue.isEmpty()) {
          Pair current = queue.poll();
          int dest = current.dest;

          if(check[dest] != 0) continue;
          check[dest] = 1;

          for(Pair next : Vmap.get(dest)) {
              int compareVal = answer[dest] + next.val;

              if(answer[next.dest] > compareVal) {
                  answer[next.dest] = compareVal;
                  queue.add(new Pair(next.dest, answer[next.dest]));
              }
          }
      }

      for(int i: answer) {
          if(i >= MAX) {
              System.out.println("INF");
          }
          else{
              System.out.println(i);
          }
      }
   }
}

class Pair implements Comparable<Pair>{
    int dest;
    int val;
    public Pair(int d, int v) {
        this.dest =d;
        this.val = v;
    }
    @Override
    public int compareTo(Pair o) {
        return Integer.compare(this.val, o.val);
    }
}

 

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!