[Algorithm] 다익스트라(Dijkstra) 알고리즘이란? (feat.Swift)

안녕하세요 Foma 👟 입니다!

 

오늘은 그래프 문제에서 아주 빈번하게 사용되는 다익스트라라는 알고리즘에 대해서 알아보겠습니다.

 

바로 시작할게요!

---

다익스트라란? 🤔

 

나무 위키에는 다음과 같이 정의되어있습니다.

 

"음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다."

 

쉽게 말하면 한 정점에서 다른 정점으로 이동할 때 가장 빠른 길을 찾아주는 알고리즘이에요.

---

그래프 설명

 

다음과 같은 그래프가 있다고 가정하겠습니다.

 

시작 정점은 1로 목표 정점을 4로 두었을 때 가장 가까운 거리는 몇일까요?

 

1 -  5 - 4 로 가는 경우가 3 + 1 = 4로 가장 가까운 길이겠죠?

 

이렇게 간단히 보이는 경로는 눈으로 쉽게 찾을 수 있지만 복잡한 경로일수록 찾기가 어려워질 것입니다.

 

이 때 다익스트라 알고리즘을 적용하는 것인데요.

 

시작 정점에서 다른 정점으로 가는 모든 거리를 최댓값으로 설정합니다.

 

그리곤 시작 정점과 연결된 정점의 거리로 업데이트 해줍니다

.

시작 정점과 연결된 정점과 연결된 정점들을 순회하면서 더 짧은 거리로 업데이트 해줍니다.

 

1번과 연결된 2번 정점과 연결된 정점을 순회하면서 2를 거쳐가는 것과 1번에서 직접 가는 것을 비교하여

 

더 짧은 거리로 경로와 거리를 업데이트 해줍니다.

이런식으로 모든 경로를 탐색하여 시작 정점에서 다른 정점으로 가는 가장 짧은 거리를 모두 업데이트 해줍니다.

---

코드 설명

 

아래와 같이 정점의 갯수, 시작 정점,연결 정보,경로를 저장할 배열,거리를 저장할 배열을 만들어줍니다.

 

//정점의 갯수
var n = 5
//시작 정점
var start = 1
//연결된 정보
var connections = [[1,2,1],[1,3,19],[1,4,10],[1,5,3],[2,3,30],[2,4,2],[2,5,7],[3,4,26],[3,5,4],[4,5,1]]
//경로를 저장할 배열
var allRoutes = (0...n).map{[$0]}
//거리를 저장할 배열(초기 값은 Int의 최댓값으로 설정)
var allDistances = Array(repeating: Int.max, count: n+1)

 

다음과 같이 다익스트라 함수를 만들어줍니다.

 

먼저 시작 정점에 있는 거리를 0으로 설정하고

 

큐와 while문을 이용해서 각 정점 그리고 연결된 정점들을 BFS 방식으로 순회해줍니다.

 

만약 중간에 거쳐서 가는 것이 직접 가는 것보다 거리가 짧다면 allDistances의 거리와 allRoutes의 경로를 새롭게 바꿔줍니다.

 

//다익스트라로 시작 정점에서 가장 가까운 거리로 업데이트해줌.
func dijkstra() {
    //자기 자신과의 거리는 0
    allDistances[start] = 0
    //시작 인덱스를 담은 큐를 만들어줌.
    var queue:[Int] = [start]
    //큐가 모두 없어질때까지 반복
    while !queue.isEmpty {
        //큐의 가장 첫번째 값을 저장하면서 삭제해줌.
        let first = queue.removeFirst()
        //연결 정보에서 큐의 첫번째 값이 있는 것들로 필터링 해줌.
        let filterNodes = connections.filter{$0[0] == first || $0[1] == first}
        //필터링한 것들을 순회
        for node in filterNodes {
            //첫번째 값이 아닌 것을 other로 설정
            let connectionNode = node[0] == first ? node[1] : node[0]
            //만약 Int 최댓값이라면 continue
            if allDistances[first] == Int.max {continue}
            //첫번째 값에 거리를 더한 것이 원래 있는 값보다 작다면
            if allDistances[first]+node[2] < allDistances[connectionNode] {
                //첫번째 값에 거리를 더한 것으로 업데이트
                allDistances[connectionNode] = allDistances[first]+node[2]
                //첫번째 큐에 있는 루트를 저장함.
                var newRoute = allRoutes[first]
                //현재 노드를 추가해줌.
                newRoute.append(connectionNode)
                //현재 노드를 새로운 경로로 바꿔줌.
                allRoutes[connectionNode] = newRoute
                //현재 노드를 큐에 넣어줌.
                queue.append(connectionNode)
            }
        }
    }
}

 

이렇게 다익스트라 알고리즘을 실행해주면 아래와 같이 allDistances엔 1에서 각 정점별 가장 짧은 거리가 담겨있고

 

allRoutes엔 가장 짧은 거리로 가는 경로가 순서대로 담기게 됩니다!

dijkstra()
print(allDistances) //[9223372036854775807, 0, 1, 7, 3, 3]
print(allRoutes) //[[0], [1], [1, 2], [1, 5, 3], [1, 2, 4], [1, 5]]

---

관련문제

 

프로그래머스 배달

 

코딩테스트 연습 - 배달

 

프로그래머스 가장 먼 노드

 

코딩테스트 연습 - 가장 먼 노드