[JAVA] 다익스트라 알고리즘 기본 틀 (#5972 택배배송)

[JAVA] 다익스트라 알고리즘 기본 틀 (#5972 택배배송)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static final int INF = 999999999; static int sum = 0; static List> graph = new ArrayList<>(); static int[] distance; static boolean[] visited; static class Node implements Comparable { int idx; int dist; Node(int idx, int dist) { this.idx = idx; this.dist = dist; } @Override public int compareTo(Node o) { return this.dist - o.dist; } } public static void dijkstra(int start) { PriorityQueue queue = new PriorityQueue<>(); distance[start] = 0; queue.add(new Node(start, 0)); while(!queue.isEmpty()) { Node e = queue.poll(); if(visited[e.idx]) { continue; } visited[e.idx] = true; for (Node linkedNode : graph.get(e.idx)) { if(e.dist + linkedNode.dist < distance[linkedNode.idx]) { distance[linkedNode.idx] = e.dist + linkedNode.dist; queue.add(new Node(linkedNode.idx, distance[linkedNode.idx])); sum += linkedNode.dist; } } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer stk = new StringTokenizer(br.readLine()); int N = Integer.parseInt(stk.nextToken()); int M = Integer.parseInt(stk.nextToken()); for(int i = 0; i < N; i++) { graph.add(new LinkedList<>()); } distance = new int[N]; visited = new boolean[N]; Arrays.fill(distance, INF); for(int i = 0; i < M; i++) { stk = new StringTokenizer(br.readLine()); int u = Integer.parseInt(stk.nextToken()); int v = Integer.parseInt(stk.nextToken()); int w = Integer.parseInt(stk.nextToken()); graph.get(u - 1).add(new Node(v - 1, w)); graph.get(v - 1).add(new Node(u - 1, w)); } dijkstra(0); System.out.println(distance[N - 1]); } }

그 이름도 유명한 다익스트라 알고리즘이다

작동 알고리즘을 한번 알아보자..

다음과 같은 양방향 그래프가 있다고 생각해 보자. 1번 노드부터 탐색을 시작한다.

1번 노드와 2번 4번 노드가 연결되어있기 때문에 최단경로를 업데이트 해준다

이후, 방문하지 않은 노드 중에서 가장 가중치가 낮은 노드로 이동한다

이후, 2번 노드에서 갈 수 있는 4번, 3번 노드의 최단경로를 업데이트 한다

위와 같은 과정의 반복이다.

2번노드에서 갈 수 있는 최단노드인 4번 노드로 이동 후 업데이트 반복

5번노드로 이동

6번노드로 이동

3번노드로 이동 -> 모든 노드를 방문했다!

비로소 우리는 가중치가 있는 그래프에서 1번 노드에서 출발했을때 N번 노드로 도착할 수 있는 최단 거리를 구할 수 있게 되었다.

이론은 대충 뭔소리를 지껄이는지 이해가 되는 것 같은데,

이걸 구현을 하라고 하니 갑자기 가슴이 답답해지고 손발이 떨려온다.

어떻게 해야할까?

코드를 살펴보자..

// static final int INF = 999999999; // public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer stk = new StringTokenizer(br.readLine()); // 데이터 입력 및 배열 초기화 int N = Integer.parseInt(stk.nextToken()); int M = Integer.parseInt(stk.nextToken()); for(int i = 0; i < N; i++) { graph.add(new LinkedList<>()); } distance = new int[N]; // 최단거리를 담아놓을 배열 visited = new boolean[N]; // 방문여부 체크 Arrays.fill(distance, INF); // 최단거리 배열은 INF로 초기화한다. // 연결 그래프 생성 // u - 1, v - 1을 하는 이유 => 0번 인덱스부터 시작하기 위함 for(int i = 0; i < M; i++) { stk = new StringTokenizer(br.readLine()); int u = Integer.parseInt(stk.nextToken()); // 출발점 int v = Integer.parseInt(stk.nextToken()); // 도착점 int w = Integer.parseInt(stk.nextToken()); // 가중치 graph.get(u - 1).add(new Node(v - 1, w)); // "양방향" 그래프 graph.get(v - 1).add(new Node(u - 1, w)); // "양방향" 그래프 } dijkstra(0); // K번 노드부터 탐색을 시작 System.out.println(distance[N - 1]); }

최단거리 정보를 저장할 distance 배열은 INF로 초기화를 해두어야 한다!

INF는 static final을 이용하여 엄청 큰 수로 세팅해둔다.

* INF를 Integer.MAX_VALUE로 설정하면 추후 최단거리 비교를 할때 오버플로우가 발생하게 된다

대충 융통성 있게 세팅할것! 알잘딱깔센

from http://sedangdang.tistory.com/106 by ccl(A) rewrite - 2021-09-03 15:00:30