[백준/JAVA] 1753번: 최단경로

🔺 문제

1753번: 최단경로

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static int V, E, K;
    public static int[] D;           // 최단 거리 배열
    public static boolean visited[]; // 방문 배열
    
    public static ArrayList<ArrayList<Edge>> A; // 인접 리스트
    public static PriorityQueue<Edge> pq = new PriorityQueue<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        V = Integer.parseInt(st.nextToken());   // 정점
        E = Integer.parseInt(st.nextToken());   // 간선
        
        K = Integer.parseInt(br.readLine());    // 시작점
        
        visited = new boolean[V + 1];        
        
        // 최단 거리 배열 초기화
        D = new int[V + 1];
        Arrays.fill(D, Integer.MAX_VALUE);
        
        // 인접 리스트 초기화
        A = new ArrayList<>();
        for(int i = 0 ; i <= V ; i++) {
            A.add(new ArrayList<>());
        }
        
        for(int i = 1 ; i <= E ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            
            A.get(u).add(new Edge(v, w));
        }
        
        
        // 다익스트라 수행
        pq.add(new Edge(K, 0)); // K를 시작점으로 설정
        D[K] = 0;
        
        while(!pq.isEmpty()) {
            Edge current = pq.poll();
            int c_ver = current.vertex;
            if(visited[c_ver]) continue;    // 중복 방지
            visited[c_ver] = true;
            
            for(int i = 0 ; i < A.get(c_ver).size() ; i++) {
                Edge tmp = A.get(c_ver).get(i);
                
                int next  = tmp.vertex;
                int value = tmp.value;
                
                // 최소 거리로 업데이트 (연결 노드 거리 리스트 값 > 선택 노드의 거리 리스트 값 + 에지 가중치인 경우)
                if(D[next] > D[c_ver] + value) {
                    D[next] = D[c_ver] + value;
                    pq.add(new Edge(next, D[next]));
                }
            }
        }
        
        // 거리 배열 출력
        for(int i = 1 ; i <= V ; i++) {
            if(visited[i])
                System.out.println(D[i]);
            else
                System.out.println("INF");
        }
    }
}
 
// 가중치 있는 그래프 담기 위한 클래스 별도 구현
class Edge implements Comparable<Edge> {
    int vertex, value;
    
    Edge(int vertex, int value) {
        this.vertex = vertex;
        this.value  = value;
    }
    
    // 우선 순위 큐 정렬 기준
    public int compareTo(Edge e) {
        if(this.value > e.value) return 1;
        else    return -1;
    }
}

✅ 해결 아이디어
✔ 모든 정점 간 최단 거리 계산 알고리즘 ⇨ 다익스트라  : BFS랑 유사 & 우선순위 큐 사용-
    - 기존에 있는 값이 신규 값보다 작을 경우, 갱신하지 않음
     : (연결 노드 거리 리스트 값 > 선택 노드의 거리 리스트 값 + 에지 가중치)인 경우 업데이트

 

💥 유의사항

⇨ 다익스트라, 꼭 우선순위 큐 사용해야 함. (일반 큐 쓰면 최단거리 보장 못 하므로)

⇨ Edge 클래스 내에 compareTo 메소드를 꼭 구현해줘야 우선순위 큐가 비교 작업함. (안 하면 컴파일 에러)

⇨ 54-65번째 줄 : 아래처럼 바꿔도 됨

for(Edge next : A.get(c_ver)) {
    if(D[next.vertex] > D[c_ver] + next.value) {
        D[next.vertex] = D[c_ver] + next.value;
        pq.add(new Edge(next.vertex, D[next.value]));
    }
}

⇨ 88-91번째 줄 : return(this.value, e.value)로 한 줄로 써도 된다.

 

---

🔺 다른 풀이들

- 우선순위 큐, 최솟값 정렬 부분이 다르심

1)

@Override
public int compareTo(Edge e) {
	return this.value - e.value;
}

[백준 1753 : JAVA] 최단경로 / 다익스트라

 

2)

PriorityQueue<Edge> pq = new PriorityQueue<Edge>((o1, o2) -> Integer.compare(o1.value, o2.value));

백준 1753 자바 최단거리 다익스트라 알고리즘 시간복잡도 JAVA

 

 

- 설명이 아주 굿. (복습용)

[백준 1753] 최단경로 -Java코드 (Dijkstra)★★★

---

💬 느낀 점

재밌따

 

 

1회독	2회독	3회독	4회독	5회독
V	6.23	9.22

 

 

( + 6.23 2회독)

방문 배열이 필요 없옸네...만

더 정확히 하려면 방문 배열 만들어두고 방문 여부 판단하는 게 좋을 것 같돠

 

🎈 기존에 있는 값이 신규 값보다 작을 경우, 갱신하지 않음
 : (연결 노드 거리 리스트 값 > 선택 노드의 거리 리스트 값 + 에지 가중치)인 경우 업데이트

import java.util.*;
import java.io.*;
 
public class Main {
    static int V, E, K;
    static int INF = Integer.MAX_VALUE;
    
    static ArrayList<Node>[] A; // 인접 리스트
    static int[] D;             // 최단 거리 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        
        V = Integer.parseInt(st.nextToken());   // 정점
        E = Integer.parseInt(st.nextToken());   // 간선
        
        K = Integer.parseInt(br.readLine());    // 시작 정점
        
        // 인접 리스트 초기화
        A = new ArrayList[V + 1];
        for(int i = 1 ; i <= V ; i++) {
            A[i] = new ArrayList<>();
        }
 
        // 최단 거리 배열 초기화
        D = new int[V + 1];
        Arrays.fill(D, INF);
        D[K] = 0;
        
        while(E --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            
            A[u].add(new Node(v, w));
        }
        
        dijkstra(K);
        
        for(int i = 1 ; i < D.length ; i++) {
            sb.append(D[i] == INF ? "INF" : D[i]).append("\n");
        }
        
        System.out.println(sb);
    }
    
    private static void dijkstra(int num) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(num, 0));   // 큐에 탐색 시작점 추가
        
        while(!pq.isEmpty()) {
            Node now = pq.poll();
           // 🔔 연결 노드 거리 리스트 값 > 선택 노드의 거리 리스트 값 + 에지 가중치인 경우, 업데이트
            for(Node next : A[now.node]) {
                if(D[next.node] > D[now.node] + next.cost) {
                    D[next.node] = D[now.node] + next.cost;
                    pq.add(new Node(next.node, D[next.node]));
                }
            }
        }        
    }
}
 
class Node implements Comparable<Node> {
    int node, cost;
    
    public Node(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
    
    // 🔔 우선순위 큐에서 사용 시 오름차순 정렬
    @Override
    public int compareTo(Node n) {
        return this.cost - n.cost;
    }
}
 

 

 

 

(+ 9.22 3회독)

import java.util.*;
import java.io.*;
 
public class Main {
    static int INF = Integer.MAX_VALUE;
    
    static int V, E, start;
    static ArrayList<Node>[] A;
    
    static int[] dist;  // 최단거리 배열
    static PriorityQueue<Node> pq = new PriorityQueue<>();  // 우선순위 큐
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        V = Integer.parseInt(st.nextToken());   // 정점
        E = Integer.parseInt(st.nextToken());   // 간선
        start = Integer.parseInt(br.readLine());
        
        // 초기화
        A = new ArrayList[V + 1];
        for(int i = 1 ; i <= V ; i++) {
            A[i] = new ArrayList<>();
        }
        
        dist = new int[V + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        
        // 간선 정보 입력 받기
        for(int i = 0 ; i < E ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            
            A[u].add(new Node(v, w));
        }
        
        dijkstra(start);
        
        for(int i = 1 ; i <= V ; i++) {
            sb.append(dist[i] == INF ? "INF" : dist[i]).append("\n");
        }
        System.out.println(sb);
    }
    
    private static void dijkstra(int num) {
        pq.add(new Node(num, 0));
        
        while(!pq.isEmpty()) {
            Node now = pq.poll();
            
            for(Node next : A[now.e]) {
                if(dist[next.e] > dist[now.e] + next.v) {
                    dist[next.e] = dist[now.e] + next.v;
                    pq.add(new Node(next.e, dist[next.e]));
                }
            }
        }
    }
}
 
class Node implements Comparable<Node> {
    int e, v;
    
    public Node(int e, int v) {
        this.e = e; this.v = v;
    }
    
    @Override
    public int compareTo(Node node) {
        return this.v - node.v;
    }
}

 

 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바