[백준][KOTLIN][14889] 스타트와 링크

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

14889번: 스타트와 링크

문제 풀이

1. 팀의 수 N 에 대해서 N/2 의 개수를 구하는 조합의 경우의 수를 DFS 를 이용하여 구한다.

2. visit 배열을 이용하여 방문된 index 를 startTeam 이라고 생각하고 방문하지 않은 index 를 linkTeam 이라고 생각한다.

2-1. 내가 짠 코드에서는 방문 배열 visit 를 이용하지 않고 startTeam/linkTeam 을 List 에 저장하여 코딩하여 좀 더 복잡해 졌다.

3. 2번에서 구해진 startTeam/linkTeam을 이용하여 능력치의 최소 값을 구한다.

코드

import java.io.*

var result14889 = Int.MAX_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val input = Array(N) {
        IntArray(N) {
            0
        }
    }

    repeat(N) {
        input[it] = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    }

    val visit = BooleanArray(N) {
        false
    }

    val result = mutableListOf<Int>()
    dfs(N, input, visit, 0, 0, result)
    println(result14889)
}

fun dfs(N: Int, input: Array<IntArray>, visit: BooleanArray, start: Int, depth: Int, result: MutableList<Int>) {
    // 탈출 조건...
    // 팀이 결성된 상황이므로 team map 에 저장한다.
    if (depth == N / 2) {
        // startTeam 과 linkTeam 을 각각 저장해도 되지만
        // visit 배열의 true 가 starTeam 이고 false 가 linkTeam 이라고 생각하고 계산할 수 있다.
        val startTeam = result.toMutableList()
        val linkTeam = mutableListOf<Int>()

        for (i in 0 until N) {
            if (startTeam.contains(i)) continue

            linkTeam.add(i)
        }

        //println("startTeam : $startTeam")
        //println("linkTeam : $linkTeam")
        //println("getResult : ${getResult(input, startTeam, linkTeam)}")

        result14889 = Math.min(result14889, getResult(input, startTeam, linkTeam))
        return
    }

    for (i in start until N) {
        if (!visit[i]) {
            visit[i] = true
            result.add(i)
            dfs(N, input, visit, i, depth + 1, result)
            visit[i] = false
            result.removeLast()
        }
    }
}

fun getResult(input: Array<IntArray>, startTeam: MutableList<Int>, linkTeam: MutableList<Int>): Int {
    return Math.abs(getStartTeamResult(input, startTeam) - getLinkTeamResult(input, linkTeam))
}

fun getStartTeamResult(input: Array<IntArray>, startTeam: MutableList<Int>): Int {
    var result = 0
    for (i in 0 until startTeam.size - 1) {
        for (j in i + 1 until startTeam.size) {
            result += input[startTeam[i]][startTeam[j]] + input[startTeam[j]][startTeam[i]]
        }
    }

    return result
}

fun getLinkTeamResult(input: Array<IntArray>, linkTeam: MutableList<Int>): Int {
    var result = 0
    for (i in 0 until linkTeam.size - 1) {
        for (j in i + 1 until linkTeam.size) {
            result += input[linkTeam[i]][linkTeam[j]] + input[linkTeam[j]][linkTeam[i]]
        }
    }

    return result
}