[코드트리/NOVICE HIGH] 네비게이션 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

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();
    static StringBuilder tmpSb = 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);
 
        System.out.println(tmpSb);
    }
    
    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]));
                    
                    for(int i = 1 ; i < dist.length ; i++) {
                        tmpSb.append(dist[i] == INF ? "INF" : dist[i]).append(" ");
                    }
                    tmpSb.append("\n");
                }
            }
        }
    }
}
 
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;
    }
}

 

📍 입력값

6 10
1
1 2 2
1 3 5
1 4 1
2 3 3
4 3 3
4 5 1
3 6 5
3 5 1
5 6 2
2 4 2

📍 최단 거리 배열 업데이트 결과 출력용

 

---

💬 느낀 점

다익스트라 복습....

얼마 전 코테에서 보고 못 풀어서 아쉬웠던....ㅠ

 

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

---

(참고)

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