[개념 정리] 최단 거리

최단 거리는 어떻게 구할 수 있을까요?

 

이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다.

 

최단 거리

최단거리 알고리즘은 그래프 상의 두 정점 사이의 거리가 최소가 되는 경로를 찾는 알고리즘입니다.

 

BFS를 사용해도 최단 거리를 구할 수 있는거 아닌가요?

 

BFS는 가중치가 같은 그래프에서 최단 거리 알고리즘으로 사용할 수 있습니다.

가중치가 다를 경우엔 최단거리 알고리즘을 사용해야 합니다.

 

가중치가 다른 경우에 BFS로 최단거리를 찾을 수 없는 예시는 다음과 같습니다.

A → C로 이동할 때, BFS로 하는 경우 14가 나오게 됩니다.

하지만, 최단 거리는 A → B → D → C로 6이 나와야 합니다.

 

최단거리 알고리즘엔 어떤게 있을까요?

 

코딩테스트에선 주로 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이 사용됩니다.

 

다익스트라 알고리즘

 

다익스트라 알고리즘은 양의 가중치를 가지는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 입니다.

u → {a,b,c} 우선순위 큐를 사용해서 현재 방문할 정점 중 가장 비용이 작은 경로를 우선 선택하고, 거리 배열을 갱신하여 최단 경로를 찾는 방식입니다.

 

시간 복잡도는 최악의 경우 모든 간선에 대해 우선순위큐를 집어 넣어야 하기 때문에 E개의 간선에 대해 우선순위 큐를 기바으로 최단거리 정점을 추출하는데 logE가 들기 때문에 ElogE가 됩니다.

 

E는 방향성이 있는 완전 그래프에서 V(V-1)이라는 특징을 가집니다.

V개의 정점이 존재할때, 각 정점마다 (V-1)개의 간선이 있기 때문에 Vx(V-1)개가 존재합니다.

따라서, ElogV^2가 되고 이는 2ElogV이며 최종적으로 ElogV가 됩니다.

 

즉, ElogE도 되고 ElogV도 됩니다.

 

다익스트라 적용

 

백준 최소비용 구하기

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

 

풀이 코드

public class Main {

    private static int N;
    private static int M;
    private static List<List<Node>> graph = new ArrayList<>();
    private static int[] dist;

    private static final int MAX_VALUE = 100_000_001;

    public static void main(String[] args) throws IOException {

        // 입력받는 값이 단방향인지 양방향인지 잘 판단해야 합니다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        dist = new int[N + 1];

        Arrays.fill(dist,MAX_VALUE);

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

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            graph.get(start).add(new Node(end, weight));
        }


        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        System.out.println(findPath(start,end));
    }

    private static int findPath(int start, int end) {

        PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> o1.weight - o2.weight);
        pq.add(new Node(start, 0));
        dist[start] = 0;

        while(!pq.isEmpty()) {
            Node cur = pq.poll(); // 무조건 최단 경로

            if(cur.number == end) {
                return dist[end];
            }

            for(int i = 0; i < graph.get(cur.number).size(); i++) {
                Node next = graph.get(cur.number).get(i);
                int newDist = dist[cur.number] + next.weight;
                if(dist[next.number] > newDist) {
                    dist[next.number] = newDist;
                    pq.add(new Node(next.number, newDist));
                }
            }
        }

        return dist[end];
    }

    public static class Node {
        int number;
        int weight;

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

 

다익스트라 알고리즘의 핵심 코드는 아래와 같습니다.

PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> o1.weight - o2.weight);
        pq.add(new Node(start, 0));
        dist[start] = 0;

        while(!pq.isEmpty()) {
            Node cur = pq.poll(); // 무조건 최단 경로

            if(cur.number == end) {
                return dist[end];
            }

            for(int i = 0; i < graph.get(cur.number).size(); i++) {
                Node next = graph.get(cur.number).get(i);
                int newDist = dist[cur.number] + next.weight;
                if(dist[next.number] > newDist) {
                    dist[next.number] = newDist;
                    pq.add(new Node(next.number, newDist));
                }
            }
        }

 

우선순위 큐를 사용해서 현재 노드와 제일 가까운 거리를 가진 이동할 노드를 선택하고, dist[다음 이동할 노드]의 거리와 dist[현재 노드] + + 가중치의 값을 비교해서 더 작은 경우를 계속 갱신해 나갑니다.

 

출력 결과

 

 

플로이드 - 워셜 알고리즘

플로이드 - 워셜 알고리즘은 모든 정점에서 모든 정점 까지의 최단 경로를 구하는 알고리즘 입니다.

 

음수 가중치가 있는 그래프에서도 사용이 가능하지만, 음수 사이클이 존재하는 경우엔 사용할 수 없습니다.

모든 노드 쌍 (i,j)에 대해, 노드 k를 경유했을 때의 최단 경로를 구하고 갱신하는 방식으로 구합니다.

 

노드 i에서 j까지의 경로가 존재할 때 노드 k를 경유하는 경우가 더 짧은 경로라면 해당 경로로 갱신합니다.

dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

 

 

플로이드 -  워셜 적용

백준 맥주 마시면서 걸아가기

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

 

이 문제는 굳이 플로이드 - 워셜 알고리즘을 사용해서 풀지 않아도 됩니다. BFS도 가능합니다.

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static int t;
    private static int n;
    private static int[][] dist;
    private static final int INF = 10_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();

        t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            n = Integer.parseInt(br.readLine());
            int total = n + 2;

            int[][] locations = new int[total][2];
            dist = new int[total][total];

            for (int i = 0; i < total; i++) {
                st = new StringTokenizer(br.readLine());
                locations[i][0] = Integer.parseInt(st.nextToken()); // x
                locations[i][1] = Integer.parseInt(st.nextToken()); // y
            }

            for (int i = 0; i < total; i++) {
                Arrays.fill(dist[i], INF);
                dist[i][i] = 0;
            }

            for(int i = 0; i < total; i++) {
                for(int j = 0; j < total; j++) {
                    if(i != j && go(locations[i], locations[j])) { // 1000m 이하인 경우에만 이어줍니다.
                        dist[i][j] = 1;
                    }
                }
            }

            for(int k = 0; k < total; k++) {
                for(int i = 0; i < total; i++) {
                    for(int j = 0; j < total; j++) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }

            if(dist[0][total - 1] != INF) {
                sb.append("happy\n");
            }else {
                sb.append("sad\n");
            }
        }

        System.out.println(sb);
    }

    private static boolean go(int[] p1, int[] p2) {
        return Math.abs(p1[0] - p2[0])  + Math.abs(p1[1] - p2[1]) <= 1000;
    }
}

 

 

플로이드 - 워샬 알고리즘에서 핵심인 부분은 아래와 같은 코드입니다.

            for(int k = 0; k < total; k++) {
                for(int i = 0; i < total; i++) {
                    for(int j = 0; j < total; j++) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }

 

 

쉽게 말해, i → j로 바로 가는 경로와 i → k → j로 가는 경로를 매번 비교하면서, 최단 거리를 갱신해주는 것입니다.

 

 

출력 결과

 

 

벨만 - 포드 알고리즘

벨만 - 포드 알고리즘은 음의 가중치가 있고 음수 사이클이 있는 그래프에서 단일 출발점 최단 경로를 구하는 알고리즘입니다.

음수 사이클이 존재하는 것도 판단할 수 있습니다.

 

문제에서 타임머신, 블랙홀, 과거로 돌아갈 수 도 있다는 워딩이 있는 경우 벨만 포드 사용을 고려해봐야 합니다.

 

원리

 

벨만 - 포드는 모든 간선을 반복적으로 확인하면서 최단 경로를 갱신합니다.

 

1. 초기화 : 출발 노드에서 출발 노드까지의 거리는 0으로 설정한 후, 나머지 노드들은 무한대로 초기화 합니다.

2. 최단 경로 갱신 : 모든 간선을 V - 1번 반복하면서 검사해 현재 경로가 기존 경로보다 짧으면 해당 경로를 갱신합니다.

3. 음수 사이클 확인 : 최단 경로가 확정된 후에도, 다시 모든 간선을 검사하여 최단 경로가 더 짧아지는 경로가 있는 경우, 이는 음수 사이클이 존재함을 의미합니다.

 

시간 복잡도는 모든 간선에 대해 V번 확인하기 때문에 O(V*E)의 시간 복잡도를 가집니다.

벨만 - 포드 적용

 

백준 웜홀

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

 

package 백준.웜홀;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    // 음수 사이클이 존재하는지 구하는 문제

    private static int tc;
    private static List<Edge> edges;
    private static final int INF = 10_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(tc-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            edges = new ArrayList<>();

            for(int i = 0; i < m; i++) { // 도로
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());
                edges.add(new Edge(start, end, weight));
                edges.add(new Edge(end, start, weight));
            }

            for(int i = 0; i < w; i++) { // 블랙홀
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());
                edges.add(new Edge(start, end, -weight));
            }

            boolean hasCycle = bellmanFord(n);

            sb.append(hasCycle ? "YES\n" : "NO\n");
        }

        System.out.println(sb);
    }

    public static boolean bellmanFord(int n) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        boolean updated = false;
        for(int i = 1; i <= n; i++) {
            updated = false;
            for(Edge edge: edges) {
                if(dist[edge.end] > dist[edge.start] + edge.weight) {
                    dist[edge.end] = dist[edge.start] + edge.weight;
                    updated = true;
                }
            }
            if(!updated) break;
        }

        if(updated) {
            for(int i = 1; i <= n; i++) {
                for(Edge edge: edges) {
                    if(dist[edge.end] > dist[edge.start] + edge.weight) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    public static class Edge {
        int start;
        int end;
        int weight;

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

 

핵심 코드는 아래와 같습니다.

public static boolean bellmanFord(int n) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        boolean updated = false;
        for(int i = 1; i <= n; i++) {
            updated = false;
            for(Edge edge: edges) {
                if(dist[edge.end] > dist[edge.start] + edge.weight) {
                    dist[edge.end] = dist[edge.start] + edge.weight;
                    updated = true;
                }
            }
            if(!updated) break;
        }

        if(updated) {
            for(int i = 1; i <= n; i++) {
                for(Edge edge: edges) {
                    if(dist[edge.end] > dist[edge.start] + edge.weight) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

 

출력 결과

 

 

정리

 

• BFS는 가중치가 같은 그래프에서 최단 경로를 찾을 수 있지만, 가중치가 다르면 다익스트라, 벨만-포드, 플로이드-워셜과 같은 최단 거리 알고리즘을 사용해야 합니다.
• 다익스트라 알고리즘은 우선순위 큐를 사용하여 현재 방문할 정점 중 가장 비용이 작은 경로를 선택하며, 시간 복잡도는 O(E log V)입니다.
• 벨만-포드 알고리즘은 모든 간선을 반복적으로 확인하여 최단 거리를 갱신하며, 음수 가중치를 포함한 그래프에서도 사용 가능하지만, 시간 복잡도는 O(V * E)입니다.