Algorithm + 코테) 다익스트라 알고리즘을 이용하여 "배달" 문제 풀기

다익스트라 알고리즘??

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주는 탐색 알고리즘이며 gps에 이용된다.

작동과정

1. 출발 노드 선정
2. 출발 노드 기준 각 노드의 최소 비용 저장
3. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택
4. 해당 노드를 거치는 경우를 고려하여 다시 갱신
5. 3~4번 반복

예제

https://school.programmers.co.kr/learn/courses/30/lessons/12978

문제 설명

문제 해석

1. N은 총 마을의 개수, K는 배달 가능한 최대 거리
2. road: Array<IntArray> IntArray를 가지는 배열이며 각 IntArray는 세자리이다. 첫 두 숫자는 이어져있는 마을들의 숫자, 세번째는 그 길을 이용할 시 걸리는 시간이다.
3. 1번 마을부터 배달을 할때 어떤 마을까지 주문을 받을 수 있을까?

알고리즘

1. 첫시도: dfs 이용

fun dfs(node: Node, visited: Array<Boolean>, sum: Int) {
    if(visited[node.num]) {
        return
    }

    if(minTime[node.num] > sum) {
        minTime[node.num] = sum
    }

    visited[node.num] = true
    node.next.forEach {
    	dfs(nodes[it.first], visited, sum+it.second)
    }
    visited[node.num] = false
}

모든 경로를 확인하다 보니 시간초과가 떴다..

2. 다익스트라 이용
   1) Node를 선언

class Node(var num: Int) {
        val next = mutableSetOf<Pair<Int, Int>>() //Pair(nextNum, time)
    }

   2) 주어진 정보 가공

val nodes = Array<Node>(N+1) { Node(-1) }
        (1..N).forEach {
            nodes[it].num = it
        }
        val minTime = Array<Int>(N+1) { Int.MAX_VALUE }
        val done = Array<Boolean>(N+1) { false }

        road.forEach {
            val num1 = it[0]
            val num2 = it[1]
            val time = it[2]
            nodes[num1].next.add(Pair(num2, time))
            nodes[num2].next.add(Pair(num1, time))
        }

   3) dfs 함수 정의

fun dfs(node: Node, from: Int, fromEx: Int) {
            if(minTime[node.num] < fromEx) {
                return
            }
            minTime[node.num] = fromEx
            
            for(ele in node.next) {
                if(ele.first == from) continue
                
                dfs(nodes[ele.first], node.num, fromEx + ele.second)
            }
        }

   4) 이용

dfs(nodes[1], -1, 0)
        minTime.forEachIndexed { i, it ->
            println("$i: $it")
            if(it <= k) answer++
        }
        
        return answer