[Java] 백준 1753 : 최단경로

문제 링크

1.

다익스트라 알고리즘. 처음 접해보는 알고리즘이다. 유튜브 영상과 해답을 보며 공부하였다.

 

자료구조 시험칠 때 친구랑 얘기하다가 다익스트라 관련 얘기가 나왔었는데, 나는 그게 뭐냐고 안 배웠다고 하고 친구는 그걸 왜 모르냐고 중요한 건데 했던 웃픈 사연이 있는 알고리즘이다.

우리 교수님은 안 알려주셨는데 다른 교수님 수업에서는 가르쳐줬다고 한다.

 

중요한 알고리즘이다.

흔히 우리 주변에서 접할 수 있는 지도의 최단 경로를 구할 때도 이 알고리즘이 적용된다.

 

오늘 배우긴했지만 또 복습하자.

 

 

2.

그래프를 인접 행렬로 구성하면 안 된다.

문제의 조건 범위가 $0\leq V\leq20000$ 인데, 인접 행렬로 구성하게 되면 $20000\times20000=$ 대략 4억으로 메모리 초과가 난다. 또한, 최악의 경우 간선이 하나일 때 불필요한 연산을 하게 되므로 비효율적이다.

 

인접 리스트를 이용하자.

중요한 점은 구성을 쉽게 하기 위해 리스트 안에 리스트를 넣는 방식을 사용한다.

 

다익스트라 알고리즘은 다이나믹 프로그램이라 할 수 있다.

최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다.

하나의 최단 거리를 구할때 이전의 구했던 최단 거리 정보를 활용한다.

 

 

문제에 대한 설명은 아래 참고 블로그에 상세하게 적혀있다.

 

3.

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

public class Main {
    private static final int INF = Integer.MAX_VALUE;
    static int v, e, start;
    static List<List<Node>> list = new ArrayList<>();
    static int[] dist;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();
        start = sc.nextInt();

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

        // 인접리스트 초기화
        for (int i = 0; i < e; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            list.get(u).add(new Node(v, w));
        }

        dist = new int[v + 1];
        Arrays.fill(dist, INF);

        dijkstra(start);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= v; i++) {
            if (dist[i] == INF)
                sb.append("INF\n");
            else
                sb.append(dist[i] + "\n");
        }

        System.out.println(sb);
        sc.close();
    }

    static void dijkstra(int start) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        boolean[] visited = new boolean[v + 1];

        q.offer(new Node(start, 0));
        dist[start] = 0;

        while (!q.isEmpty()) {
            int cur = q.poll().end;

            if (visited[cur])
                continue;
            visited[cur] = true;

            for (Node next : list.get(cur)) {
                if (dist[next.end] > dist[cur] + next.weight) {
                    dist[next.end] = dist[cur] + next.weight;
                    q.offer(new Node(next.end, dist[next.end]));
                }
            }
        }
    }
}

class Node implements Comparable<Node> {
    int end, weight;

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

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

 

 

4.

어렵다. 복습하자.

 

[참고] https://dragon-h.tistory.com/20

[참고] https://www.youtube.com/watch?v=611B-9zk2o4&t=1040s