알고리즘 유형9. 최단경로

최단경로

가장 짧은 경로, 길찾기

 

최단경로 유형은 "한 지점에서 다른 지점까지의 최단경로",  "모든 지점에서 다른 모든 지점까지의 최단경로" 등으로 나눠볼 수 있다.

 

이러한 유형은

1. 다익스트라 알고리즘
2. 플로이드워셜 알고리즘
3. 그래프 알고리즘(BFS)
4. greedy & DP 알고리즘
5. 벨만 포드 알고리즘

등  정말 다양한 알고리즘으로 풀이할 수 있다.

 

다만 지금까지의 경험으로는 최단경로 문제는 왠만하면? 1~3번으로 거의 다 해결이 되는 느낌이었다.

---

최단경로에는 가중치가 있는데 비용(cost), 거리(distance), 무게(weight) 이런식으로 있을 수 있다.

 

다익스트라

• 현재 정점에서 다른 특정 정점
• 가중치가 있는 경우
• O(NlogN)

플로이드워셜

• 모든 정점에서 모든정점
• 가중치가 있는 경우
• O(N^3) (ex) 사다리타기..?)

BFS

• 현재 정점에서 다른 특정 정점
• 가중치가 없거나 똑같을 경우
• 인접행렬 사용시 O(N^2), 인접리스트 사용시 O(N+E)
  • E : 완전탐색하는 그래프 알고리즘에서 발생하는 연산의 개수

보다시피 시간복잡도만 보면 BFS를 이용하는게 유리하다.

 

다만, 그래프 알고리즘에는 가중치를 대응할 기능이 없으므로 가중치가 있는 경우 다익스트라 or 플로이드워셜을 사용한다.

---

다익스트라의 경우 priority queue를 사용해서 O(NlogN) 의 시간복잡도를 가질 수 있다.

 

Priority Queue

가장 우선순위가 높은 데이터 추출

 

다익스트라에서 priority queue는 간선의 가중치를 기준으로 데이터를 추출한다.

 

추가 문제 : 백준 1238

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

 

: 본인 마을 = 본인번호 N, 각 마을을 연결하는 M개의 단방향 도로, 파티를 주최하는 X번 마을

모든 사람들은 본인 마을에서 파티가 열리는 마을에 갔다가 다시 본인 마을로 돌아오는 최단 거리를 구해야한다.

그 최단거리들 중에 가장 긴것을 출력

package 최단경로_ch09;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
// 다익스트라
// 그래프 자료구조 : 인접 리스트
public class BaekJoon_1238_2{
    static int N, M, X, max;
    static final int INF = Integer.MAX_VALUE;
    static List<List<Node>> goList = new ArrayList<>(); // X 로 가는 
    static List<List<Node>> backList = new ArrayList<>(); // X  에서 집으로 되돌아 오는
    static PriorityQueue<Node> pqueue = new PriorityQueue<>( (n1, n2) -> n1.t - n2.t );
    static int[] goCost;
    static int[] backCost;
    static boolean[] visit;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        for (int i = 0; i <= N; i++) {
            goList.add(new ArrayList<>());
            backList.add(new ArrayList<>());
        }
        
        goCost = new int[N + 1];
        backCost = new int[N + 1];
        visit = new boolean[N + 1];
        
        for (int i = 0; i < M; i++) { // 간선
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            
            goList.get(a).add(new Node(b, t));
            // a -> b 길 중에 분명히 집 -> X 로 가는 최단 경로가 존재할 것이고 역으로 뒤집으면 그 길이 X -> 집 다익스트라로 처리
            backList.get(b).add(new Node(a, t));
        }
        
        // 풀이
        max = Integer.MIN_VALUE;
        
        dijkstra(goList, goCost);
        dijkstra(backList, backCost);
        
        for (int i = 1; i <= N; i++) {
            max = Math.max(max, goCost[i] + backCost[i]);
        }
        
        System.out.println(max);
    }
    
    static void dijkstra(List<List<Node>> list, int[] cost) {
    	// cost, visit 초기화
        Arrays.fill(cost, INF);
        Arrays.fill(visit, false);
        
        // 시작점 X
        cost[X] = 0;
        pqueue.offer(new Node(X, 0));
        
        while(! pqueue.isEmpty() ) {
            Node node = pqueue.poll();
            if( visit[node.v] ) continue;
            visit[node.v] = true;
            
            for (Node n : list.get(node.v)) {
                if( visit[n.v] ) continue;
                if( cost[n.v] > cost[node.v] + n.t ) {
                    cost[n.v] = cost[node.v] + n.t;
                    pqueue.offer(new Node(n.v, cost[n.v]));
                }
            }
        }
    }
    static class Node{
        int v; // 정점 마을(집)
        int t; // 시간
        
        Node(int v, int t){
            this.v = v;
            this.t = t;
        }
    }
}

/*
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

10
*/