[알고리즘] Dijkstra

개요

다익스트라(Dijkstra) 알고리즘은 BFS와 Dynamic Programming을 활용한 최단경로 검색 알고리즘이다. 

 

 다익스트라 알고리즘은 가중치가 존재하는 그래프의 하나의 정점에서 다른 정점들로 가는 최단 경로를 알려준다. 만약에 가중치가 존재하지 않는다면 단순 BFS를 통해서 최단 경로를 구할 수 있지만, 가중치가 존재한다면 Dijkstra를 사용할 수 있다. 다익스트라는 일반적으로 인접 행렬(O(N^2))이나 우선순위 큐(O(ElogV), E:edge, V:vertex)를 사용하여 구현한다.

 

 시작 전에 간단하게 설명하면, 다익스트라 알고리즘은 방문하지 않은 노드들 중에서 시작점으로부터 최소거리를 갖는 노드를 선택하여 노드들의 거리를 갱신하는 것을 반복하는 알고리즘이다.

 

 

 일단 시작 노드부터 탐색을 시작한다. 정점에 붙어있는 간선 중에서 시작 노드로부터의 거리가 짧은 노드부터 선택하여 그 노드에서 이웃한 노드에 가중치를 기록하는데, 처음 탐색하는 노드라면 (이전 노드까지의 가중치+간선의 가중치)를 기록하고, 재탐색하는 노드라면 (min(이전 노드까지의 가중치+간선의 가중치, 기록된 가중치))를 기록한다. 이것은 직접 이웃한 정점으로 가는 것보다 다른 정점을 가쳐서 가는 것이 더 적은 비용값을 가질 수도 있기 때문이다. 이렇게 최소 가중치를 저장하면서 탐색 대상 노드와, 그와 이웃한 노드들에 대한 갱신을 해주면 된다.

 

 

 

1. 인접 행렬을 이용한 구현 - O(N^2)

- 인접 행렬을 사용한 dp와 유사하지만, 가중치값이 0일수도 있기에 노드 간 거리를 나타내는 행렬의 초기값을 INF값으로 지정하고, i==j인 경우(대각) 초기값을 0으로 설정해준다.

- 거기에 노드들의 가중치값(시작 노드에서의 거리)을 기록하는 1차원 배열을 만들어서 가중치값을 저장해주는데, 이 역시 초기값을 INF로 설정하여 유효값 여부를 구분할 수 있게 한다.

- 마지막으로 노드의 탐색여부를 저장하는 boolean배열(visited)을 만들고 모든 노드에 대한 탐색이 한번씩 이루어지도록 하면 된다.

//N개의 노드를 탐색하려 할 경우 시작노드를 제외하고 N-1번 탐색하면 된다.
for(int i=0; i<N-1; i++) {
  for(int j=0; j<N; j++) {
    //탐색이 이루어지지 않은 노드중에서 최소 가중치를 갖는 노드 찾기
  }
  
  //찾은 노드를 방문처리하고,
  //그 노드의 인접 노드들에 대한 가중치 갱신하기
}

 

BOJ 1916) 최소비용 구하기 - 인접 행렬

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

//dijkstra (인접 행렬)
//"버스 비용이 0일수도 있다"
public class Main {

    static int N;
    static int M;
    static int[][] map;
    static int[] dp;
    static boolean[] visited;
    static final int INF = 0x3f3f3f3f;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new int[N]; //시작점에서 최소거리
        visited = new boolean[N];
        //인접 행렬, dp(거리) 무한대로 초기화
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                map[i][j] = INF;
        for(int i=0; i<N; i++)
            dp[i] = INF;

        int start, end;
        for(int i=0; i<M; i++) {
            String[] line_N = br.readLine().split(" ");
            int s = Integer.parseInt(line_N[0])-1;
            int e = Integer.parseInt(line_N[1])-1;
//            if(map[s][e]==0) >> 버스 비용이 0일수도 있다. 0이 초기화가 된것일수 있음
            if(map[s][e] == INF) //초기화되지 않은 경우
                map[s][e] = Integer.parseInt(line_N[2]);
            else { //동일 경로에 다른 값이 입력될 경우 작은 값으로 설정
                if(map[s][e]>Integer.parseInt(line_N[2]))
                    map[s][e] = Integer.parseInt(line_N[2]);
            }
        }
        String[] line_last = br.readLine().split(" ");
        start = Integer.parseInt(line_last[0])-1;
        end = Integer.parseInt(line_last[1])-1;

        //시작노드와 그 연결노드 초기값 설정
        dp[start] = 0;
        visited[start] = true;
        for(int i=0; i<N; i++) {
            if(!visited[i] && map[start][i]!=INF)
                dp[i] = map[start][i];
        }

        //모든 노드가 true될때까지 == 노드가 N개이므로 시작노드를 제외하고 N-1번
        for(int i=0; i<N-1; i++) {
            int min = Integer.MAX_VALUE; //INF로 할 경우 dp[i]가 초기화되지 않은 i만 남은 경우 문제발생가능
            int min_idx = -1;

            for(int j=0; j<N; j++) {
                if(!visited[j])
                    if(dp[j]<min) {
                        min = dp[j];
                        min_idx = j;
                    }
            }

//            for(int j=0; j<N; j++) {
//                if(!visited[j])
//                    System.out.print(j+",");
//            }
//            System.out.println();
//            System.out.println("min_idx:"+(min_idx));
            visited[min_idx] = true;
            for(int j=0; j<N; j++) {
                if(!visited[j] && map[min_idx][j] != INF) {
                    if(dp[min_idx]+map[min_idx][j]<dp[j]) {
                        dp[j] = dp[min_idx]+map[min_idx][j];
                    }
                }
            }
        }

        System.out.println(dp[end]);
    }
}

 

 

 

2. 우선순위 큐를 사용한 구현 - O(ElogV)

 인접 행렬이 아니라 우선순위 큐를 이용해서도 다익스트라 알고리즘을 구현할 수 있다. 시작점으로부터의 거리를 저장하는 1차원 배열, 탐색여부를 체크하는 1차원 배열은 인접행렬을 사용한 우선순위 큐와 동일하지만, 인접행렬을 이용했을 때는 N-1번의 반복을 거칠 때마다 아직 탐색하지 않은 노드들 중에 가중치가 가장 작은 노드를 찾아 그 노드를 탐색하는데, 우선순위 큐를 이용해서 이 과정을 대신한다. 

 

 

참고: https://www.youtube.com/watch?v=QleeV_ipB7w&ab_channel=ezsw

  시작 노드 및 그와 연결된 노드의 정보를 우선순위 큐에 넣는다. 그 후에 큐가 빌때까지 큐에서 노드를 꺼내며 최소비용을 구해가면 된다.

- 이때 우선순위 큐는 가장 낮은 가중치를 가지는 노드가 가장 높은 우선순위를 갖게 하여 낮은 가중치를 갖는 노드가 먼저 나오게 설정함으로써 전체 노드중 가장 작은 가중치(=시작점으로부터 가장 짧은 거리)를 갖는 노드를 찾는다.

(그렇게 하기 위해서 큐에는 노드와 가중치 정보가 있는 클래스가 들어가도록 한다 - 밑 코드에서는 Node클래스)

- 여기에 추가로 큐에서 꺼낸 뒤 visited여부를 체크해서 visited되지 않은 경우에만 확인하도록 한다.

 

 

 

예제 - BOJ 10282) 해킹

문제

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.

각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

 

출력

각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

 

 

 

풀이

1. 컴퓨터 간에는 가중치를 갖는 연관관계가 존재한다.

2. 해킹 시작 노드(c)가 지정되어 있다.

3. 시작 노드로부터 나머지 노드까지 감염이 되는지, 얼만큼의 시간이 걸리는지를 구해야 한다

 

문제에는 크게 위 3가지 조건이 있는데, 모두 c를 시작점으로 하는 dijkstra로 구할 수 있다. 시간복잡도를 줄이기 위해 PQ를 사용한 다익스트라를 사용하겠다.

 

PQ를 사용한 다익스트라에는 크게 다음과 같은 자료구조들이 필요하다.

 

- 연관관계를 알 수 있는 리스트 list

- 가까운 노드부터 탐색할 수 있게 도와주는 우선순위 큐 pq

- 시작 노드부터의 거리를 나타내는 1차원 배열 dist

- 탐색 여부를 알 수 있는 1차원 boolean 배열 visited

 

 

다익스트라에서 유의할 점만 정리하면 다음과 같다.

private static void dijkstra(int start) {
    dist = new int[n+1];
    visited = new boolean[n+1];
    pq = new PriorityQueue<>(new Comparator<Info>() {
        @Override
        public int compare(Info o1, Info o2) {
            return o1.time-o2.time;
        }
    });
    Arrays.fill(dist, INF);
    dist[start] = 0;
    pq.add(new Info(start, 0));

    while(!pq.isEmpty()) {
        Info cur = pq.poll();

        if (visited[cur.dest]) continue; // 이미 방문한 경우 건너뛰기
        visited[cur.dest] = true;        // 현재 노드 방문 처리

        for(int i=0; i<list[cur.dest].size(); i++){
            Info next = list[cur.dest].get(i);
            if(dist[next.dest]>dist[cur.dest]+next.time) {
                dist[next.dest] = dist[cur.dest]+next.time;
                if(!visited[next.dest]) {
                    pq.add(new Info(next.dest, dist[next.dest]));
                }
            }
        }
    }
}

 

1. 우선순위 큐는 가까운 거리부터 탐색할 수 있도록 Comparator를 사용하여 정렬기준을 설정한다.

2. 시작 노드로부터 거리를 무한대값(INF)으로 초기화하고, 시작점은 0으로 초기화한다.

3. BFS와 다르게 visited 설정을 큐에 넣은 직후에 하면 안된다. BFS는 모든 간선의 가중치가 동일하므로, 첫 방문이 곧 최단 경로 도달이 된다. 하지만 다익스트라는 나중에 도달하는 경우가 더 짧은 경우도 존재할 수 있다. 따라서 우선순위 큐에서 꺼내진 후에 방문을 확정하는 것이 옳다.

 

 

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

// 가중치 bfs -> dijkstra
// 시작 컴퓨터 ~ 나머지 컴퓨터까지 걸리는 시간의 최대값
public class Main {
    static int n, d, c;
    static ArrayList<Info>[] list;
    static PriorityQueue<Info> pq;
    static boolean[] visited;
    static int[] dist;
    static final int INF = 0x3f3f3f3f;
    static int infectedComputer, infectTime;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for(int t=0; t<T; t++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            list = new ArrayList[n+1];
            for(int i=1; i<=n; i++) {
                list[i] = new ArrayList<>();
            }
            visited = new boolean[n+1];
            infectedComputer = 0;
            infectTime = 0;

            for(int i=0; i<d; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken()); // b->a 경로
                int b = Integer.parseInt(st.nextToken());
                int s = Integer.parseInt(st.nextToken());

                list[b].add(new Info(a, s));
            }

            dijkstra(c);
            for(int i=1; i<=n; i++) {
                if(dist[i]!=INF) {
                    infectedComputer++;
                    infectTime = Math.max(infectTime, dist[i]);
                }
            }
            System.out.println(infectedComputer+" "+infectTime);
        }
    }

    private static void dijkstra(int start) {
        dist = new int[n+1];
        visited = new boolean[n+1];
        pq = new PriorityQueue<>(new Comparator<Info>() {
            @Override
            public int compare(Info o1, Info o2) {
                return o1.time-o2.time;
            }
        });
        Arrays.fill(dist, INF);
        dist[start] = 0;
        pq.add(new Info(start, 0));

        while(!pq.isEmpty()) {
            Info cur = pq.poll();

            if (visited[cur.dest]) continue; // 이미 방문한 경우 건너뛰기
            visited[cur.dest] = true;        // 현재 노드 방문 처리

            for(int i=0; i<list[cur.dest].size(); i++){
                Info next = list[cur.dest].get(i);
                if(dist[next.dest]>dist[cur.dest]+next.time) {
                    dist[next.dest] = dist[cur.dest]+next.time;
                    if(!visited[next.dest]) {
                        pq.add(new Info(next.dest, dist[next.dest]));
                    }
                }
            }
        }
    }

    static class Info {
        int dest;
        int time;
        public Info(int dest, int time) {
            this.dest = dest;
            this.time = time;
        }
    }
}

 

 

예제 - BOJ 14938) 서강그라운드

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

// n=100이므로 모든 지역에 대해서 bfs
// WA1) 간선 가중치가 다른 그래프의 경우 다익스트라 활용 (비효율적인 경로가 먼저 방문해버릴 수 있다)
// WA2) 거리 갱신시에 visited를 체크하면 안된다.
public class Main {
    static int n, m, r;
    static int[] item, dist;
    static ArrayList<Info>[] list;
    static PriorityQueue<Info> queue;
    static boolean[] visited;
    static int rst = 0;
    static final int INF = 0x3f3f3f3f;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line_1 = br.readLine().split(" ");
        n = Integer.parseInt(line_1[0]); // 지역
        m = Integer.parseInt(line_1[1]); // 수색범위
        r = Integer.parseInt(line_1[2]); // 길

        item = new int[n+1];
        list = new ArrayList[n+1];
        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }
        String[] line_2 = br.readLine().split(" ");
        for(int i=1; i<=n; i++) {
            item[i] = Integer.parseInt(line_2[i-1]);
        }

        // 거리 정보 받기
        for(int i=0; i<r; i++) {
            String[] line_r = br.readLine().split(" ");
            int s = Integer.parseInt(line_r[0]);
            int e = Integer.parseInt(line_r[1]);
            int w = Integer.parseInt(line_r[2]);
            list[s].add(new Info(e, w));
            list[e].add(new Info(s, w));
        }

        // n개의 시작점에 대해서 다익스트라를 통해서 거리를 구하고, 범위 내의 아이템 더한것의 최대값 구하기
        for(int i=1; i<=n; i++) {
            dijkstra(i);

            // 최대값 찾기
            int sum = 0;
            for(int j=1; j<=n; j++) {
                if(dist[j]<=m)
                    sum += item[j];
            }
            rst = Math.max(sum, rst);
        }

        System.out.println(rst);
    }

    private static void dijkstra(int start) {
        // 우선순위 큐 조건 설정
        queue = new PriorityQueue<>(new Comparator<Info>() {
            @Override
            public int compare(Info o1, Info o2) {
                return o1.weight-o2.weight;
            }
        }); // 가까운 것 우선순위
        // visited는 방문시가 아니라, 첫 방문시에만 체크
        visited = new boolean[n+1];
        // dist 초기화 - 시작점만 0으로
        dist = new int[n+1];
        for(int j=1; j<=n; j++) {
            dist[j] = INF;
        }
        dist[start] = 0;

        queue.add(new Info(start, 0));

        while(!queue.isEmpty()) {
            Info poll = queue.poll();
            visited[poll.dest] = true;

            // poll 한 정점의 주변 정점들만 비교해 나감
            for(int j=0; j<list[poll.dest].size(); j++) {
                Info next = list[poll.dest].get(j);
                if(dist[next.dest]>dist[poll.dest]+next.weight) {
                    dist[next.dest] = dist[poll.dest]+next.weight;
                    if(!visited[next.dest]) { // 갱신시에만 visited 체크
                        queue.add(new Info(next.dest, dist[next.dest]));
                    }
                }
            }
        }
    }

    static class Info {
        int dest;
        int weight; // dest까지 거리

        public Info(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }
}