[BOJ] 14889번 : 스타트와 링크

문제 보기

소스

kotlin

import java.util.*
import kotlin.math.abs
import kotlin.math.min

var n = 0
var result = Int.MAX_VALUE
lateinit var status: Array<IntArray>
lateinit var visited: BooleanArray

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    status = Array(n) { IntArray(n) }
    visited = BooleanArray(n)
    for (i in 0 until n) {
        for (j in 0 until n) {
            status[i][j] = nextInt()
        }
    }
    dfs(0, 0)
    println(result)
}

fun dfs(index: Int, count: Int) {
    if (count == n / 2) {
        statusGap()
        return
    }

    for (i in index until n) {
        if (!visited[i]) {
            visited[i] = true
            dfs(i + 1, count + 1)
            visited[i] = false
        }
    }
}

fun statusGap() {
    var startSum = 0
    var linkSum = 0

    for (i in 0 until n - 1) {
        for (j in i + 1 until n) {
            if (visited[i] && visited[j]) {
                startSum += status[i][j] + status[j][i]
            } else if (!visited[i] && !visited[j]) {
                linkSum += status[i][j] + status[j][i]
            }
        }
    }
    result = min(result, abs(startSum - linkSum))
}

스타트 팀과 링크 팀을 구분 짓는 자료구조를 따로 선언하지 않고 BooleanArray인 visited의 값을 통해 구분하므로 dfs 함수의 첫 번째 인자로 index를 사용하였다.