[알고리즘][KOTLIN] 다익스트라

정의

• 최단 경로를 찾는 그래프(DFS, BFS)알고리즘에서 각 경로에 가중치가 있어 최소 가중치의 경로를 찾는 알고리즘
• 그래프 알고리즘으로 경로를 탐색하고 최소 경로를 저장하기 위해 DP를 활용한다.

백준 알고리즘 연관 문제

• 1162, 1238, 1753, 1916

문제

• 아래 주어진 각 노드와 연결된 경로에서 시작 시점인 노드1에서 각 노드까지의 최단 거리를 구한다.

1. 연결된 경로와 경로의 가중치를 저장하는 maps 배열을 선언한다.(크기 : n + 1, n은 노드의 개수)
2. DP 를 이용하여 최단 거리를 저장하기 위한 distance 배열을 선언한다.(크기 : n + 1, n은 노드의 개수) 이때 distance 배열의 각 항목은 Int.MAX_VALUE 로 초기화 한다. 최소 거리를 비교하기 위해...
3. 방문을 확인하는 check 배열을 선언한다.(크기 : n + 1, n은 노드의 개수)
4. 시작 노드1의 distance 와 check 값을 저장한다.
5. 시작 노드와 인접해 있는 노드2, 4, 5 의 distance 값을 저장한다.(distance[2]=3, distance[4]=4, distance[5]=4)
6. 기준이 되는 노드(처음은 노드1)의 인접 노드 중 방문하지 않는 노드의 최소 거리 값을 찾는다. 이때 최소 거리를 DP 를 이용하여 다음 노드까지의 거리와 현재 저장된 거리 중 최소 값을 확인 한다.(distance[min] + map[min][i] < distance[i])
7. 6번 과정을 n 번 반복한다.

풀이(시작 노드1)

1. check[1] = true, distance[1] = 0
2. 시작 노드와 인접해 있는 노드까지의 거리 저장 : distance[2]=3, distance[4]=4, distance[5]=4)

3. 인접 노드까지의 거리 중 최소 값의 노드 Index 과 거리를 저장 : minIndex(2), check[minIndex] = true

4. minIndex 를 가지는 노드(2) 와 인접해 있는 노드까지 거리 중 최소 값으로 저장
5. 노드2에서 갈 수 있는 인접노드는 노드3이므로 노드3까지의 최단 거리 계산
6. 만약 distance[2(minIndex)] + maps[2(minIndx)][3] < distance[3] 이면 distance[3] 에 최소 거리를 저장 함
7. 3번 ~ 6번 과정을 방문하지 않는 노드를 찾아 반복 수행

코드

//dijkstra algorithm
fun main(args: Array<String>) {
    val g = Graph(8)
    g.input(1, 2, 3)
    g.input(1, 4, 4)
    g.input(1, 5, 4)
    g.input(2, 3, 2)
    g.input(4, 3, 1)
    g.input(4, 5, 2)
    g.input(4, 7, 6)
    g.input(5, 6, 4)
    g.input(3, 8, 3)
    g.input(7, 6, 3)
    g.input(6, 8, 2)

    g.dijkstra(1)
}

private class Graph(private val n: Int) {
    // 각 노드의 가중치 정보를 저장
    private val maps = Array(n + 1) {
        IntArray(n + 1)
    }

    // 가중치 저장
    fun input(start: Int, end: Int, weight: Int) {
        // 그래프이므로 양방향 저장
        maps[start][end] = weight
        maps[end][start] = weight
    }

    fun dijkstra(start: Int) {
        // 최단 거리를 저장하는 배열. 최소 값 비교를 위해서 MAX_VALUE 로 초기화 한다.
        val distance = IntArray(n + 1) {
            Int.MAX_VALUE
        }
        // 방문 여부를 저장하는 배열
        val check = BooleanArray(n + 1)

        // 시작 노드(1)의 distance, check 값 저장
        distance[start] = 0
        check[start] = true
        // 시작 노드와 인접해 있는 노드까지의 거리 저장
        distance[2] = maps[start][2]
        distance[4] = maps[start][4]
        distance[5] = maps[start][5]

        repeat(n) { // 노드 개수만큼 반복해서 탐색
            // 시작되는 노드에서 인접 노드까지의 거리 중 방문하지 않은 노드 중 최소 거리 노드 정보 구하기
            var minIndex = -1
            var min = Int.MAX_VALUE

            for (i in 1..n) {
                if (!check[i] && distance[i] != Int.MAX_VALUE) {
                    if (distance[i] < min) {
                        min = distance[i]
                        minIndex = i
                    }
                }
            }

            if (minIndex > 0) {
                // 위에서 구한 인접 노드 중 최소 거리의 노드를 기준으로 다음 인접 노드까지 최소 거리를 구함
                check[minIndex] = true

                for (i in 1..n) {
                    if (!check[i] && maps[minIndex][i] != 0) { // maps 배열 중 경로가 있는(0이 아닌) 것 중 방문하지 않는 것 확인
                        if (distance[minIndex] + maps[minIndex][i] < distance[i]) {
                            distance[i] = distance[minIndex] + maps[minIndex][i]
                        }
                    }
                }
            }
        }

        for (i in 1..n) {
            print("${distance[i]} ")
        }
    }
}