백준 23354번 군탈체포조 Kotlin

https://www.acmicpc.net/problem/23354

문제

---

생각하기

---

• 다익스트라와 백트래킹이 합쳐진 문제이다.

동작

부대를 기준으로 다익스트라 실행, 탈영병을 기준으로 다익스트라 실행
해당 결과가 값을 HashMap에 저장하고 백트래킹을 통해 조합을 만든 뒤 최단거리를 찾으면 된다.

결과

코드

---

import java.io.BufferedWriter
import java.io.File
import java.io.OutputStreamWriter
import java.util.*

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var totalDeserter = 0
private lateinit var board: Array<IntArray>
private lateinit var command: Coordinate
private lateinit var hashMap: HashMap<Int, Coordinate>
private lateinit var comb: IntArray
private lateinit var isVisited: BooleanArray
private lateinit var distHashMap: HashMap<Int, Array<IntArray>>
private lateinit var commandArr: Array<IntArray>
private var ans = 0

private const val INF = Int.MAX_VALUE
private val dirX = intArrayOf(-1, 0, 1, 0)
private val dirY = intArrayOf(0, 1, 0, -1)

private data class Coordinate(val x: Int, val y: Int, val cost: Int) : Comparable<Coordinate> {
    override fun compareTo(o: Coordinate): Int {
        return cost - o.cost
    }
}

fun main() {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

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

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

    commandArr = dijkstra(command) // 사령부 최단거리
    hashMap.forEach { k, v ->
        distHashMap[k] = dijkstra(hashMap[k]!!)
    }


    DFS(0, 0)

    if (ans == INF) ans = 0
    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun DFS(depth: Int, idx: Int) {
    if (totalDeserter == depth && totalDeserter >= 1) {
        var sum = 0
        val first = hashMap[comb[0]]
        sum += commandArr[first!!.x][first.y]
        var tempArr = distHashMap[comb[depth - 1]]!!
        sum += tempArr[command.x][command.y]


        for (i in 1 until depth) {
            tempArr = distHashMap[comb[i - 1]]!!
            val next = hashMap[comb[i]]
            sum += tempArr[next!!.x][next.y]
        }

        ans = Math.min(sum, ans)
        return
    }

    for (i in idx until totalDeserter) {
        if (isVisited[i]) continue
        isVisited[i] = true
        comb[depth] = i
        DFS(depth + 1, idx)
        isVisited[i] = false
    }
} // End of DFS()

private fun dijkstra(start: Coordinate): Array<IntArray> {
    var dist = Array(N) { IntArray(N) { INF } }
    val que = PriorityQueue<Coordinate>()
    val isVisited = Array(N) { BooleanArray(N) }
    que.offer(start)
    dist[start.x][start.y] = 0

    while (que.isNotEmpty()) {
        val cur = que.poll()

        if (isVisited[cur.x][cur.y]) continue
        if (dist[cur.x][cur.y] < cur.cost) continue
        isVisited[cur.x][cur.y] = true

        for (j in 0 until 4) {
            val nX = dirX[j] + cur.x
            val nY = dirY[j] + cur.y

            if (!isAble(nX, nY, isVisited)) continue

            if (dist[nX][nY] > dist[cur.x][cur.y] + board[nX][nY]) {
                dist[nX][nY] = dist[cur.x][cur.y] + board[nX][nY]
                que.offer(Coordinate(nX, nY, dist[nX][nY]))
            }
        }
    }

    return dist
} // End of dijkstra()

private fun isAble(x: Int, y: Int, isVisited: Array<BooleanArray>): Boolean {
    return x in 0 until N && y in 0 until N && !isVisited[x][y]
} // End of isAble()

private fun input() {
    N = br.readLine().toInt()
    hashMap = HashMap<Int, Coordinate>()
    totalDeserter = 0

    board = Array(N) { i ->
        val temp = br.readLine()

        StringTokenizer(temp).run {
            IntArray(N) { j ->
                var temp2 = nextToken().toInt()
                if (temp2 == -1) {
                    command = Coordinate(i, j, 0)
                    temp2 = 0
                } else if (temp2 == 0) {
                    hashMap.put(totalDeserter++, Coordinate(i, j, 0))
                }

                temp2
            }
        }
    }

    totalDeserter
    comb = IntArray(totalDeserter)
    isVisited = BooleanArray(totalDeserter)
    distHashMap = HashMap()
    ans = INF
} // End of input()