백준 - 1753 최단경로 - Java + 다익스트라

백준 최단경로 문제를 풀어보았다.

최단 경로는 대표적인 3가지 알고리즘이 있는데, 뭔가 어려워 보여서 계속 미루고 있었는데, 이번 기회에 공부해보았고 알아두면 유용하며 생각보다 어렵지 않은 알고리즘이었다.

세 가지 알고리즘에 대해서 곧 바로 문제에 적용해보면서 정리할 것이고, 이번 문제는 다익스트라를 적용하는 문제이다.

• 최단경로 풀이 알고리즘
  • 다익스트라
  • 벨만-포드
  • 플로이드 워셜 

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

1753번: 최단경로

---

문제 설명

 

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

• 방향그래프가 주어지면, 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램
• 간선에 대한 가중치는 10 이하의 자연수(양수)
• 간단하게 시작점에서 출발하는 모든 노드에 대한 최단 경로를 출력
• 노드가 2만, 간선이 30만

제한 조건에 의해 플로이드 워셜은 적용할 수 없음(시간복잡도 O(v^3))

따라서 다익스트라, 벨만 - 포드 알고리즘으로 해결할 수 있는 문제이지만, 

벨만 - 포드 알고리즘은 음수 가중치, 음수 사이클 판별 문제에 더 적합한 알고리즘이기 때문에 다익스트라를 적용하여 풀면 된다.

 

추가로 간선이 매우 30만으로 많기 때문에 인접 리스트로 그래프를 구현하여 풀도록 한다.

---

다익스트라 알고리즘

• 그래프에서 최단 거리를 구하는 알고리즘
• 출발 노드와 모든 노드 간의 최단 거리 탐색
• 에지(가중치)는 모두 양수
• 시간복잡도 O(ElogV)

 

그래프가 다음과 같이 주어졌다고 하자. (문제에선 방향그래프이지만 예제는 무방향 그래프)

https://chanhuiseok.github.io/posts/algo-47/

일단 distance 배열은 무시하자

다익스트라 알고리즘을 구현하기 위해

 

1. 인접 리스트로 그래프를 구현한다. (노드 번호, 가중치)

• 1번 노드 - (2, 5), (4, 9), (5, 1)
• 2번 노드 - (1, 5), (3, 2)
• 3번 노드 - (2, 2), (4, 6)
• 4번 노드 - (1, 9), (3, 6), (5, 2)
• 5번 노드 - (1, 1), (4, 2)

2. 최단거리 배열 distance를 생성한다. (시작점의 가중치는 0으로 초기화한다)

1	2	3	4	5
0	INF	INF	INF	INF

3. 최단 경로를 업데이트 한다 (여기가 중요)

     1. 값이 가장 작은 노드 고르기

     2. 선택된 노드에서 연결된 노드의 값을 바탕으로 다른 노드의 값을 업데이트(최단 거리 배열 업데이트)

 

최단 거리 배열 업데이트 과정

D배열에서 가장 최단 거리인 노드를 선택해 연결된 노드의 최단 경로를 업데이트 한다.

• 1번(시작)노드의 값이 최소이므로 1번 노드와 연결된 노드를 탐색

2번 노드의 값과 d[2] > d[1] + w 이면 d[2]를 업데이트 한다

다른 노드들에 대해 반복

1	2	3	4	5
0	5	INF	9	1

• 같은 노드에 대해 반복하면 안되기 때문에 (시간복잡도) 1번 노드에 대한 방문여부는 true로 변경해놓는다

---

• 이미 방문한 1번 노드를 제외하고, 가장 최단 경로의 노드를 선택한다 -> 5번 노드 선택
• 방문 처리를 하고 마찬가지로 5번과 연결된 노드들 중 최단 경로를 업데이트 한다
• d[4] < d[5] + w ? d[5]+w : d[4]

1	2	3	4	5
0	5	INF	3	1

---

• 다음 4번 노드를 방문
• 업데이트
• d[3] < d[4] + w ?

1	2	3	4	5
0	5	9	3	1

---

• 다음 2번 방문
• 업데이트

1	2	3	4	5
0	5	7	3	1

---

• 다음 3번 방문
• 업데이트 (없음)

1	2	3	4	5
0	5	7	3	1

---

4. 시작점으로 부터 각 노드까지 최단 경로 배열이 완성

1	2	3	4	5
0	5	7	3	1

의미

• 시작점(1)로 부터 i 노드 까지 최단 경로를 의미한다
• 시작점을 무엇으로하느냐에 따라 완성되는 distance 배열은 다르겠다

---

문제 풀이 코드

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

class Main{
    static class Node{
        int num, w;
        public Node(int num, int w){
            this.num=num; this.w=w;
        }
    }
    public static List<ArrayList<Node>> graph = new ArrayList<>();
    public static int[] d, visited;
    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()), e = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(br.readLine());
        for(int i=0; i<=v; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<e; i++){
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken()), n2 = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken());
            graph.get(n1).add(new Node(n2, w));
        }
        d = new int[v+1];
        visited = new int[v+1];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[k] = 0;    // 시작 노드
        dijkstra(k);
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=v; i++){
            if(d[i] == Integer.MAX_VALUE) sb.append("INF\n");
            else sb.append(d[i]+"\n");
        }
        System.out.print(sb);
        br.close();
    }
    public static void dijkstra(int start){
        Queue<Node> queue = new PriorityQueue<>((n1, n2) -> n1.w - n2.w);
        queue.offer(new Node(start, 0));
        while(!queue.isEmpty()){
            Node n = queue.poll();
            if(visited[n.num] == 1) continue;
            visited[n.num] = 1;
            for(Node node : graph.get(n.num)){
                if(d[node.num] > d[n.num] + node.w) d[node.num] = d[n.num] + node.w;
                // 업데이트 된 최소 비용으로 다음 노드로 간다
                queue.offer(new Node(node.num, d[node.num]));
            }
        }
    }
}

• 간선이 많기 때문에 인접 리스트로 구현
• 가중치를 위한 Node 클래스 객체 생성
• 현재 최단 경로인 노드를 순서로 순회하기 위해 PriorityQueue 사용, Comparator 람다식 정의
• visited를 둬서 방문한 노드는 제외

---

다익스트라 적용 문제 자체는 알고리즘만 이해한다면 쉬운것 같다.

문제 몇개를 더 풀어보고 벨만 - 포드 알고리즘과 관련된 문제를 정리해야겠다.