백준 17182번
https://www.acmicpc.net/problem/17182

문제

---

생각하기

---

• 다익스트라, 백트래킹 혼합 문제이다.

  • 두 알고리즘의 개념을 알고있다면 어렵지 않게 풀 수 있다.

• 다익스트라를 통해서 모든 노드에서 출발해서 최소거리 배열을 만들고, 이 값을 백트래킹을 통해서 최소 시간을 뽑아내면 된다.
  

동작

결과

코드

---

Kotlin

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

// input
private lateinit var br: BufferedReader

// variables
private const val INF = Int.MAX_VALUE
private var N = 0
private var K = 0
private var ans = INF

private lateinit var adjList: MutableList<MutableList<Node>>
private lateinit var dist: Array<IntArray>
private lateinit var isVisited: BooleanArray

private data class Node(var num: Int, var weight: Int) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return weight - other.weight
    } // End of compareTo()
} // End of Node class

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    for (i in 0 until N) {
        dijkstra(i)
    }

    isVisited[K] = true
    DFS(K, 0, 0, 0)
    sb.append(ans)

    return sb.toString()
} // End of solve()

private fun dijkstra(startNode: Int) {
    val pque = PriorityQueue<Node>()
    dist[startNode][startNode] = 0
    pque.offer(Node(startNode, 0))

    while (pque.isNotEmpty()) {
        val pollNode = pque.poll()

        for (nextNode in adjList[pollNode.num]) {
            if (dist[startNode][nextNode.num] > nextNode.weight + dist[startNode][pollNode.num]) {
                dist[startNode][nextNode.num] = nextNode.weight + dist[startNode][pollNode.num]
                pque.offer(Node(nextNode.num, dist[startNode][nextNode.num]))
            }
        }
    }
} // End of dijkstra()

private fun DFS(num: Int, depth: Int, index: Int, sum: Int) {
    if (sum >= ans) return
    else if (depth == N - 1) {
        ans = Math.min(ans, sum)
        return
    }

    for (i in 0 until N) {
        if (isVisited[i]) continue
        if (i == num) continue
        isVisited[i] = true
        DFS(i, depth + 1, index, sum + dist[num][i])
        isVisited[i] = false
    }
} // End of DFS()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt() // 행성의 개수
        K = nextToken().toInt() // 발사되는 행성의 위치
    }

    adjList = ArrayList()
    repeat(N) {
        adjList.add(ArrayList())
    }

    isVisited = BooleanArray(N)

    dist = Array(N) { IntArray(N) { INF } }

    for (i in 0 until N) {
        StringTokenizer(br.readLine()).run {
            for (j in 0 until N) {
                val temp = nextToken().toInt()
                if (j == i) continue

                adjList[i].add(Node(j, temp))
            }
        }
    }
} // End of input()