[Java] 백준 최단경로

1. 문제분석

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

1753번: 최단경로

방향그래프가 주어지고 모든 정점으로 최단 경로를 구하는 문제다.

이 문제는 시작 정점에 모든 정점을 탐색하는 것이므로 다익스트라를 사용했다.

또한, 출력값은 최단 경로의 경로값을 출력하면 된다.

2. 시행착오

그래프 문제를 풀어보고 싶어서 고른 문제였다.

대학교때 배운 것이 기억이 안나 답지는 안보고 알고리즘만 보고 문제를 풀어갈려고 했다.

 

1. 크루스칼

가장 먼저 생각난 것은 크루스칼이다. 최단 경로? 하면 크루스칼이라 생각했기 때문이다.

하지만 크루스칼은 시작이 처음(0 또는 1)로 고정된 상태였다. 바로 포기.

2. 프림

크루스칼 하면 다음에 생각나는 것, 프림을 찾아봤다.

프림은 시작점도 내가 정할 수 있고 정답을 맞출 수 있을 것 같았다.

하지만 경로를 구했는데 가중치를 구할 때 뭔가 이상해졌다. 이 정점을 지날 때 가중치? 되게 이상하게 구해졌다.

3. 다익스트라

마지막으로 했던건 다익스트라다. 프림과 상당히 비슷하지만 차이점이 있다고 한다.

- 다익스트라는 최단경로, 프림은 최소신장트리다.

- 프림은 무방향에서만, 다익스트라는 상관없다.

결국 최소신장트리를 구하는게 아니고 최단경로를 구하는 것이다. 다익스트라를 구현했더니 문제가 풀렸다.

3.  구현

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


class Node implements Comparable<Node> {
    int index, distance;

    Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

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

public class Solution {

    static int vertex, edge, startVertex;
    static List<List<Node>> list;
    static int[] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 첫째줄은 정점과 간선의 개수
        StringTokenizer st = new StringTokenizer(br.readLine());
        vertex = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());

        // 두번째는 시작 정점
        startVertex = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        dist = new int[vertex + 1];

        for (int i = 0; i <= vertex; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 1; i <= vertex; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        // 마지막은 각 연결된 정점과 간선의 가중치
        for (int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int sVertex = Integer.parseInt(st.nextToken());
            int eVertex = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            list.get(sVertex).add(new Node(eVertex, value));
        }
        dijkstra(startVertex);

        for (int i = 1; i <= vertex; i++) {
            if(dist[i] == Integer.MAX_VALUE) System.out.println("INF");
            else System.out.println(dist[i]);
        }
    }

    static void dijkstra(int index) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[index] = 0;
        pq.offer(new Node(index, 0));

        while (!pq.isEmpty()) {
            Node n = pq.poll();
            int vertex = n.index;
            int distance = n.distance;

            if (distance > dist[vertex]) continue;

            for (Node node : list.get(vertex)) {
                //거처가는게 빠르냐 그냥이 빠르냐
                if (distance + node.distance < dist[node.index]) {
                    dist[node.index] = distance + node.distance;
                    pq.offer(new Node(node.index, dist[node.index]));
                }
            }
        }
    }
}

다익스트라를 그대로 구현했다. 다익스트라의 작동방식은 다음과 같다.

1. 시작정점을 우선순위 큐에 넣어준다. 가중치 배열또한 초기화 한다

2. 큐에서 값을 꺼내고 연결가능한 정점을 탐색한다.

3. 연결했을 때 기존에 있는 가중치 배열보다 더 작다면 큐에 넣고 갱신한다.

4. 참고

https://codingnojam.tistory.com/46

[Algorithm] 다익스트라(Dijkstra) 알고리즘을 Java로 구현해보자! (BOJ-1753 최단경로)

(다익스트라를 찾으러 간건데 예제가 백준이였을줄은 몰랐다..)