[백준] 최단경로 - Java 자바

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

사용개념: 다익스트라

 

 

다익스트라를 통해 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다.

최단거리를 저장하는 배열과 우선순위 큐를 이용해 구현한다.

 

 

전체 코드

import java.io.*;
import java.util.*;

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

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

        @Override
        public int compareTo(Node other) {
            return weight - other.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());    // 시작 정점

        // 인접 리스트 생성
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보 입력
        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());
            graph.get(u).add(new Node(v, w));
        }

        // 최단 거리 배열
        int[] distance = new int[V+1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[K] = 0;

        // 우선순위 큐
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(K, 0));

        while (!pq.isEmpty()) {
            Node current = pq.remove();

            if (distance[current.vertex] < current.weight) continue;

            for (Node next : graph.get(current.vertex)) {
                int cost = distance[current.vertex] + next.weight;

                if (cost < distance[next.vertex]) {
                    distance[next.vertex] = cost;
                    pq.add(new Node(next.vertex, cost));
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (distance[i] == Integer.MAX_VALUE) {
                sb.append("INF\n");
            } else {
                sb.append(distance[i] + "\n");
            }
        }
        System.out.println(sb);
    }
}

 

 

Node 클래스

PriorityQueue 사용을 위해 Comparable 인터페이스 구현

• PriorityQueue에서 노드들을 가중치 기준으로 정렬하기 위해 필요
• Comparable 인터페이스를 구현하여 노드 간 비교 방법을 정의

// PriorityQueue 사용 예시
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(1, 4));
pq.offer(new Node(2, 3));
Node smallest = pq.poll();  // 가중치가 3인 노드가 먼저 나옴

 

 

 

다익스트라를 자바로 구현하는 연습도 필요할 것 같아서 풀어봤다.