[알고리즘] 다익스트라(Dikstra Algorithm)

1.  다익스트라 알고리즘

• 그래프의 한 노드에서 각 모든 노드까지 최단거리를 구하는 알고리즘
  • 음의 가중치를 가지면 최소 비용의 음의 무한대 발산, 그리디 알고리즘 적용 불가능 등이 발생.
• 초기 모델은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다). 일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다.
  • 연결 그래프 : 모든 두 꼮짓점 사이에 경로가 존재하는 그래프
  • 희소 그래프 : 밀집 그래피의 반대
  • 밀집 그래프 : 간선의 수가 최대에 가까운 그래프 : 간선 개수 = 정점의 개수 ^2와 근사하다면 밀집 그래프 이다.
• 매커니즘
  • 기본적으로 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘
  • 기본적으로 두 단계를 반복하여 임의의 노드에서 각 모든 노드까지의 최단거리를 구한다.
    • 1. 방분하지 않은 노드 중에서 가장 비용이 적은 노드 선택(그리디 알고리즘)
    • 2. 선택 노드에서 갈 수 있는 노드의 비용 갱신(다이나믹 프로그래밍)

2.  예시

위 그래프를 예시로 다익스트라 알고리즘을 진행해 본다.

방문하지 않은 노드의 집합 Before, 최소비용을 계산하는 배열 D를 준비해보자, After는 방문한 노드의 집합으로 코드 작성방법에 따라 필요 없을 수 도 있다. 참고로 D의 초기값들은 0가 아니라 inf나 매우 큰 값으로 초기화 해주어야 한다.

 1. 초기화 단계

A가 시작점임으로 A까지 가는 비용은 0 이다. 그리고 방문하지 않은 노드 중에 A가 비용이 제일 적음으로 다음 단계의 기준점은 A가 된다.

 

2. 알고리즘 적용

A를 기준으로 방문가능한 B,C,D까지 가는 비용을 정리했다. 그리고 다음 기준점은 방문하지 않은 노드중에 비용이 제일 적은 B를 기준으로 한다.

 

B를 기준으로 C,F를 방문할 수 있다. 특히 C의 경우 B를 거쳐가면 9라는 비용이 발생하지만 A에서 바로 가면 5이기 때문에 수정하지 않는다. 반대로 F는 B를 거쳐 12의 비용이 발생했다. 그리고 다음 기준점은 D가 된다.

 

D를 기준으로 C, E를 갈 수있다. 그리고 C는 기존의 비용 5보다 낮은 4로 갱신된다.

이런 방식으로 쭉쭉 진행한다....

 

 최종적으로는 위와 같이 노드들까지 도달하는 비용을 정리할 수 있다.

 

3.  프로그래머스 문제(배달) 해결

• 문제는 링크를 참조합시다.

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        //갈 수 있는 길들을 2차원 배열에 정리
        int[][] roads = new int[N + 1][N + 1];
        for (int i = 0; i < road.length; i++) {
            System.out.println(road[i][0] + " " + road[i][1]);
            System.out.println(road[i][2]);

            if ((roads[road[i][0]][road[i][1]] > road[i][2]) || (roads[road[i][0]][road[i][1]] == 0)) {
                roads[road[i][0]][road[i][1]] = road[i][2];
                roads[road[i][1]][road[i][0]] = road[i][2];
            }
        }

        //여기서 부터 idx 기준으로 번호를 작성한다.
        //0이면 1번 노드 이다. roads는 제외한다.
        
        //특정 노드까지 도달할 시간을 저장할 배열
        //문제 상 최대 값보다 높은 숫자로 초기화
        //시작 노드는 0으로 초기화한다.        
        int[] elapsedTime = new int[N];
        Arrays.fill(elapsedTime, 500001);
        elapsedTime[0] = 0;

        //방문했는지 저장하는 노드, 방문하면 true로 바꾼다.
        boolean[] visited = new boolean[N];

        //마을의 개수만큼 루프를 돈다.
        for (int k = 0; k < N; k++) {
            
            //최소 시간과 그 시간을 가지는 기준 노드를 position에 저장한다.
            int leastTime = 50001;
            int position = 0;
            //leastTime보다 적은 비용으로 갈 수 있는 노드만 파악한다. 없다면 시작노드가 기준이 된다.
            for (int i = 1; i < visited.length; i++) {
                if (visited[i] == false && elapsedTime[i] < leastTime) {
                    leastTime = elapsedTime[i];
                    position = i;
                }
            }
            
            //기준 노드까지 걸리는 시간을 저장한다.
            int baseTime = elapsedTime[position];
            
            //기준노드 에서 갈 수 있는 길들(0이상의 비용을 가진 roads의 원소) 중에서
            //길들을 통해 갈 수 있는 노드의 비용이 현재 비용보다 적은 경우에는 바꿔주고 아니면 냅둔다.
            for (int i = 1; i < N; i++) {
                if (roads[position + 1][i + 1] > 0 && roads[position + 1][i + 1] + baseTime < elapsedTime[i]) {
                    elapsedTime[i] = roads[position + 1][i + 1] + baseTime;
                }
            }
            //방문한거를 체크한다.
            visited[position] = true;

        }

        // 경과시간을 파악하여 정답 개수를 뽑아낸다.
        for (int i = 0; i < elapsedTime.length; i++) {
            if (elapsedTime[i] <= K) {
                answer++;
            }
        }

        return answer;
    }
}

 

4.  참고

• 프로그래머스 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

• 다익스트라 알고리즘 참고 : https://sskl660.tistory.com/59

[Java]다익스트라 알고리즘(Dijkstra Algorithm)