[2023-04-16] 스타트와 링크(Kotlin)

 

 

문제 링크: https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

문제 풀이는 쉬웠다고 생각합니다.

 

하지만 시간복잡도를 줄이는데에 있어서 많이 힘들었습니다.

 

package sixteenthDay
import java.io.*
import java.util.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    var valueArr = Array(n+1){Array(n+1){0} } // 입력받은 점수
    
    repeat(n){ // 점수 각각 2차원 배열에 추가
        val string = StringTokenizer(br.readLine())
        for (index in 1..n){
            valueArr[it+1][index] = string.nextToken().toInt()
        }
    }
    
    val visit = Array(n+1){false} // 방문 배열
    val ans = Array(n){0} //숫자를 뽑아서 저장할 배열
    
    var finalValue = Int.MAX_VALUE //최소값을 저장할 변수
    
    fun dfs(num: Int){
        if (num == n){ 
            var start = 0
            var link = 0
            // 배열의 0번 째부터 n/2 까지는 link 계산
            // 나머지는 start 계산
            for (index in 0 until n/2){
                for (index1 in index+1 until n/2){
                    link += valueArr[ans[index+n/2]][ans[index1+n/2]] + valueArr[ans[index1+n/2]][ans[index+n/2]]
                    start += valueArr[ans[index]][ans[index1]] + valueArr[ans[index1]][ans[index]]
                }
            }
            // 두 절대값을 뺀 값
            val v = Math.abs(start - link)
            // 0일 때는 출력 후 종료
            if (finalValue == 0){
                println(0)
                System.exit(0)
            }
            // 이전 값보다 작으면 저장
            if (finalValue >= v)
                finalValue = v
            return
        }
        for (index in 1 ..n){
            if (!visit[index]){
                visit[index] = true
                ans[num] = index
                dfs(num+1)
                visit[index] = false
            }
        }
    }
    dfs(0)
    println(finalValue)
}

 

답안은 맞은 것 같았지만, 시간초과가 계속해서 떴습니다.

 

계속 시도해보다, 결국은 다른 분의 코드를 참고하게 되었습니다.

 

 

package Any
import java.io.*
import java.util.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val arr = Array(n+1){Array(n+1){0} }
    repeat(n){i ->
        val token = StringTokenizer(br.readLine())
        for (index in 1..n){
            arr[i+1][index] = token.nextToken().toInt()
        }
    }
    val v = Array(n+1){false}
    var min = Int.MAX_VALUE
    
    fun dfs(num: Int, idx: Int){
        if (num == n/2){
            var teamStart = 0
            var teamLink = 0
            for (index in 1 until n){
                for (index1 in index+1..n){
                    if (v[index] && v[index1]){ //방문한 값들은 start
                        teamStart += arr[index][index1] + arr[index1][index]
                    }
                    else if (!v[index] && !v[index1]){ // 방문하지 않은 것들은 link
                        teamLink += arr[index][index1] + arr[index1][index]
                    }
                }
            }
            val diff = Math.abs(teamStart-teamLink)
            if (diff==0){
                println(0)
                System.exit(0)
            }
            min = Math.min(diff,min)
            return
        }
        for (index in idx..n){
            if (!v[index]){
                v[index] = true
                dfs(num+1, index+1)
                v[index] = false
            }
        }
    }
    dfs(0, 1)
    println(min)

}

 

다른 분의 코드를 확인해보고 나서야 제 코드가 비효율적이라는 것을 깨달았습니다.

 

 

예를 들어 N이 4일 때,

 

1 2 3 4,   1 2 4 3 ... 등 결과는 같지만, 중복되는 경우의 수가 많이 계산됩니다.

 

 

 

제 스스로 해내지 못해 기분이 좋지 않았습니다.

 

답안 코드를 따라 작성해보면서 백트래킹의 원리에 대해 다시 공부해보는 시간을 가졌습니다.