[BOJ] 1753.최단경로(다익스트라).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

다익스트라 알고리즘을 구현하는 문제이다.

다익스트라에 대한 자세한 설명은 링크에서 확인해보자!

#. Code_v1

priorityQueue를 사용하지 않고 해결한 경우

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer;   public class BOJ1753 {       static class Edge {         int v, weight;           public Edge(int v, int weight) {             this.v = v;             this.weight = weight;         }              }          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         int V = Integer.parseInt(st.nextToken());    // 정점의 개수         int E = Integer.parseInt(st.nextToken());    // 간선의 개수         int K = Integer.parseInt(br.readLine()) - 1;    // 시작 정점(번호를 1부터 input)         final int INF = Integer.MAX_VALUE;                  // 인접 리스트 준비         List<Edge>[] adj = new ArrayList[V];         for (int i = 0; i < V; i++)              adj[i] = new ArrayList<>();                  // 간선 정보 입력         for (int i = 0; i < E; i++)  {             st = new StringTokenizer(br.readLine());             adj[Integer.parseInt(st.nextToken()) - 1].add(new Edge(Integer.parseInt(st.nextToken()) - 1,                      Integer.parseInt(st.nextToken())));         }                  // dist 배열         int[] dist = new int[V];         boolean[] checked = new boolean[V];                  // dist 배열을 INF로 초기화         Arrays.fill(dist, INF);         // 시작점은 0으로 변경         dist[K] = 0;                  for (int i = 0; i < V; i++) {             // check되지 않았으면서,             // 현재(i)정점으로부터 dist 값이 제일 작은 정점(j)의 번호 찾기             int min = INF, cur = -1;             for (int j = 0; j < V; j++) {                 if(!checked[j] && dist[j] < min) {                     min = dist[j];                     cur = j;                 }             }               // 현재 정점으로부터 dist 값이 제일 작은 정점을 못 찾았으면             if(cur == -1) break;                          // 찾은 정점(j)으로부터 갈 수 있는 경로가 이미 알고 있는 dist보다 작다면 갱신             // index가 가지고 있는 모든 간선을 검사             for (Edge next : adj[cur]) {                 // check되지 않았으면서 다음 노드 까지의 거리가                 // 나까지 거리 + 나로부터 다음 노드까지 거리보다 작다면 갱신                  if(!checked[next.v] && dist[next.v] > dist[cur] + next.weight) {                     dist[next.v] = dist[cur] + next.weight;                 }             }                          // 체크 완료             checked[cur] = true;         }                  for (int i = 0; i < V; i++) {             if(dist[i] == INF) System.out.println("INF");             else System.out.println(dist[i]);         }     }      }   Colored by Color Scripter

cs

#. Code_v2

선택된 정점으로부터 뻗는 모든 간선을 다 priorityQueue에 넣은 후 가중치가 가장 작은 간선을 뽑는 방법

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.PriorityQueue; import java.util.StringTokenizer;   public class BOJ1753_v2 {       static class Edge implements Comparable<Edge> {         int v, weight;           public Edge(int v, int weight) {             this.v = v;             this.weight = weight;         }           @Override         public int compareTo(Edge o) {             return Integer.compare(this.weight, o.weight);         }              }          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         int V = Integer.parseInt(st.nextToken());    // 정점의 개수         int E = Integer.parseInt(st.nextToken());    // 간선의 개수         int K = Integer.parseInt(br.readLine()) - 1;    // 시작 정점(번호를 1부터 input)         final int INF = Integer.MAX_VALUE;                  // 인접 리스트 준비         List<Edge>[] adj = new ArrayList[V];         for (int i = 0; i < V; i++)              adj[i] = new ArrayList<>();                  // 간선 정보 입력         for (int i = 0; i < E; i++)  {             st = new StringTokenizer(br.readLine());             adj[Integer.parseInt(st.nextToken()) - 1].add(new Edge(Integer.parseInt(st.nextToken()) - 1,                      Integer.parseInt(st.nextToken())));         }              // dist 배열         int[] dist = new int[V];         boolean[] checked = new boolean[V];                  // dist 배열을 INF로 초기화         Arrays.fill(dist, INF);         // 시작점은 0으로 변경         dist[K] = 0;                  PriorityQueue<Edge> pQ = new PriorityQueue<>();         pQ.add(new Edge(K, 0));         Edge cur = null;                  while(!pQ.isEmpty()) {             // check되지 않았으면서,             // 현재(i)정점으로부터 dist 값이 제일 작은 정점(j)의 번호 찾기             cur = pQ.poll();             if(checked[cur.v]) continue;                          // 찾은 정점(j)으로부터 갈 수 있는 경로가 이미 알고 있는 dist보다 작다면 갱신             // index가 가지고 있는 모든 간선을 검사             for (Edge next : adj[cur.v]) {                 // check되지 않았으면서 다음 노드 까지의 거리가                 // 나까지 거리 + 나로부터 다음 노드까지 거리보다 작다면 갱신                  if(!checked[next.v] && dist[next.v] > dist[cur.v] + next.weight) {                     dist[next.v] = dist[cur.v] + next.weight;                     pQ.add(new Edge(next.v, dist[next.v]));                 }             }                          // 체크 완료             checked[cur.v] = true;         }                  for (int i = 0; i < V; i++) {             if(dist[i] == INF) System.out.println("INF");             else System.out.println(dist[i]);         }     }      }   Colored by Color Scripter

cs

#. Code_v3

dist 배열 값 자체를 우선순위큐를 통해 제일 작은 가중치를 뽑는 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ1753_v3 {
 
    static class Edge implements Comparable<Edge> {
        int v, totalWeight;
 
        public Edge(int v, int weight) {
            this.v = v;
            this.totalWeight = weight;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.totalWeight, o.totalWeight);
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());    // 정점의 개수
        int E = Integer.parseInt(st.nextToken());    // 간선의 개수
        int K = Integer.parseInt(br.readLine()) - 1;    // 시작 정점(번호를 1부터 input)
        final int INF = Integer.MAX_VALUE;
        
        // 인접 리스트 준비
        List<Edge>[] adj = new ArrayList[V];
        for (int i = 0; i < V; i++) 
            adj[i] = new ArrayList<>();
        
        // 간선 정보 입력
        for (int i = 0; i < E; i++)  {
            st = new StringTokenizer(br.readLine());
            adj[Integer.parseInt(st.nextToken()) - 1].add(new Edge(Integer.parseInt(st.nextToken()) - 1, 
                    Integer.parseInt(st.nextToken())));
        }
    
        // dist 배열
        int[] dist = new int[V];
        boolean[] checked = new boolean[V];
        
        // dist 배열을 INF로 초기화
        Arrays.fill(dist, INF);
        // 시작점은 0으로 변경
        dist[K] = 0;
        
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.add(new Edge(K, dist[K]));
        Edge cur = null;
        
        while(!pQ.isEmpty()) {
            // check되지 않았으면서,
            // 현재(i)정점으로부터 dist 값이 제일 작은 정점(j)의 번호 찾기
            cur = pQ.poll();
            if(checked[cur.v]) continue;
            
            // 찾은 정점(j)으로부터 갈 수 있는 경로가 이미 알고 있는 dist보다 작다면 갱신
            // index가 가지고 있는 모든 간선을 검사
            for (Edge next : adj[cur.v]) {
                // check되지 않았으면서 다음 노드 까지의 거리가
                // 나까지 거리 + 나로부터 다음 노드까지 거리보다 작다면 갱신 
                if(!checked[next.v] && dist[next.v] > cur.totalWeight + next.totalWeight) {
                    dist[next.v] = cur.totalWeight + next.totalWeight;
                    pQ.add(new Edge(next.v, dist[next.v]));
                }
            }
            
            // 체크 완료
            checked[cur.v] = true;
        }
        
        for (int i = 0; i < V; i++) {
            if(dist[i] == INF) System.out.println("INF");
            else System.out.println(dist[i]);
        }
    }
    
}