[백트래킹 / Kotlin] BOJ 14889 - 스타트와 링크

문제

풀이 언어

Kotlin

코드

import java.lang.Integer.min
import java.util.*
import kotlin.math.abs
import kotlin.system.exitProcess

lateinit var board: Array<Array<Int>>
lateinit var visited: Array<Int>
var min_value = Int.MAX_VALUE
var n = 0

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    board = Array(n) { Array(n) { nextInt() } }
    visited = Array(n) { 0 }

    search(0, 0)
    println(min_value)
}

fun search(index: Int, depth: Int) {
    if (depth == n / 2) {
        calculate()
        return
    }

    for (i in index until n) {
        if (visited[i] == 0) {
            visited[i] = 1
            search(i + 1, depth + 1)
            visited[i] = 0
        }
    }
}

fun calculate() {
    var start = 0
    var link = 0

    for (i in 0 until n - 1) {
        for (j in i until n) {
            if (visited[i] == 1 && visited[j] == 1) {
                start += board[i][j]
                start += board[j][i]
            } else if (visited[i] == 0 && visited[j] == 0) {
                link += board[i][j]
                link += board[j][i]
            }
        }
    }

    val score = abs(start - link)

    if (score == 0) {
        println(score)
        exitProcess(0)
    }

    min_value = min(score, min_value)
}

풀이 방법

개인적으로 백트래킹 어떻게 적용할지를 발견하지 못해서 앞서 작성한 골드 문제보다 어려웠다. 우선 2개의 팀 (스타트팀, 링크팀) 으로 나누어야 한다. 방문 지점을 스타트팀 으로 두고 방문하지 않는 지점을 링크팀 으로 두고 문제를 해결했다.

 

1. 2개의 팀으로 나누므로 depth == n / 2 인 경우에 점수 계산

fun search(index: Int, depth: Int) {
    if (depth == n / 2) {
        calculate()
        return
    }

    for (i in index until n) {
        if (visited[i] == 0) {
            visited[i] = 1
            search(i + 1, depth + 1)
            visited[i] = 0
        }
    }
}

 

2. 방문한 지점을 스타트팀으로, 방문하지 않은 지점을 링크팀으로 두고 점수 계산

    for (i in 0 until n - 1) {
        for (j in i until n) {
            if (visited[i] == 1 && visited[j] == 1) {
                start += board[i][j]
                start += board[j][i]
            } else if (visited[i] == 0 && visited[j] == 0) {
                link += board[i][j]
                link += board[j][i]
            }
        }
    }

    val score = abs(start - link)
    min_value = min(score, min_value)

 

3. 점수의 차이가 0이면 최소값이므로 DFS를 진행하지 않고 종료

    if (score == 0) {
        println(score)
        exitProcess(0)
    }

결과