[알고리즘] 백준 1753 최단경로 -최단경로, 다익스트라, 그래프- 자바

 

www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

 

백준 최단경로 단계별풀기의 첫번째 문제입니다. 

최단경로의 가장 베이스적인 문제입니다.

 

풀이는 주석에 적어놓았습니다.

또 설명은 다음 블로그에서 그림과 함께 잘 해놓으셨습니다. ㅎㅎ

dragon-h.tistory.com/20

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

 

 

[Java]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static ArrayList<Node>[] list;
    private static int v;
    private static int e;
    private static int start;
    private static int[] distance;
    private static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        v = sc.nextInt(); //정점개수
        e = sc.nextInt(); //간선개수
        start = sc.nextInt(); //시작정점
        list = new ArrayList[v + 1]; //정점 인접리스트
        distance = new int[v + 1]; //시작점과 다른 정점간의 최단경로
        for (int i = 1; i <= v; i++) {
            list[i] = new ArrayList<>();
        }
        //초기화
        Arrays.fill(distance, INF);
        distance[start] = 0;
        for (int i = 0; i < e; i++) {
            int u = sc.nextInt(); //출발
            int v = sc.nextInt(); //도착지
            int w = sc.nextInt(); //가중치
            list[u].add(new Node(v, w));
        }
        dijkstra();
        for (int i = 1; i <= v; i++) {
            if (distance[i] == INF) {
                System.out.println("INF");
            } else {
                System.out.println(distance[i]);
            }
        }
    }

    private static void dijkstra() {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(start, 0));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int vertex = node.vertex;
            int weight = node.weight;
            if (distance[vertex] < weight) { //지금께 더 가중치가 크면 갱신할 필요가 없다.
                continue;
            }
            for (int i = 0; i < list[vertex].size(); i++) {//해당 정점과 연결된 것들 탐색
                int vertex2 = list[vertex].get(i).vertex;
                int weight2 = list[vertex].get(i).weight + weight;
                if (distance[vertex2] > weight2) { //지금께 더 최단경로라면 갱신해준다.
                    distance[vertex2] = weight2;
                    queue.add(new Node(vertex2, weight2));
                }
            }
        }
    }

    private static class Node implements Comparable<Node> { //우선순위큐로 성능개선(안하면 시간초과뜸)
        int vertex;
        int weight;

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

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    }
}

 

 

[2020-11-27 복습]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static ArrayList<Node>[] list;
    private static int V;
    private static int E;
    private static int[] distance;
    private static int start;
    private static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        E = sc.nextInt();
        start = sc.nextInt();
        list = new ArrayList[V + 1];
        distance = new int[V + 1];
        for (int i = 1; i <= V; i++) {
            list[i] = new ArrayList<>();
        }
        Arrays.fill(distance, INF);
        distance[start] = 0;
        for (int i = 0; i < E; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            list[u].add(new Node(v, w));
        }
        dijkstra();
        for (int i = 1; i <= V; i++) {
            if (distance[i] == INF) {
                System.out.println("INF");
            } else {
                System.out.println(distance[i]);
            }
        }
    }

    private static void dijkstra() {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(start, 0));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (distance[node.vertex] < node.edge) {
                continue;
            }
            for (int i = 0; i < list[node.vertex].size(); i++) {
                Node node2 = list[node.vertex].get(i);
                int vertex2 = node2.vertex;
                int edge2 = node2.edge + node.edge;
                if (distance[vertex2] > edge2) {
                    distance[vertex2] = edge2;
                    queue.add(new Node(vertex2, edge2));
                }
            }
        }

    }

    public static class Node implements Comparable<Node> {
        int vertex;
        int edge;

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

        @Override
        public int compareTo(Node o) {
            return edge - o.edge;
        }
    }
}

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!