[BOJ/백준][Silver2] 10971 : 외판원 순회2 (Kotlin)

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

10971번: 외판원 순회 2

 

 

 

[난이도] Silver2
[유형] 백트래킹

[풀이]
N제한이 10밖에 안되기 때문에 순회할 수 있는 모든 경우를 백트래킹 해주면 된다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.min
import java.util.*
var N=0
val cost = Array(10,{Array(10){0}})
val visit = Array(10){false}
var ans=987654321
fun sol(start:Int,n:Int,sum:Int,cnt:Int){
    visit[n]=true
    //println("n:${n}, sum:${sum}, cnt:${cnt}")
    if(cnt==N && cost[n][start]>0){
        ans=min(ans,sum+cost[n][start])
    }
    for(i in 0 until N){
        if(cost[n][i]>0 && !visit[i]){
            sol(start,i,sum+cost[n][i],cnt+1)
        }
    }
    visit[n]=false
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    N=readLine().toInt()
    for(i in 0 until N){
        var ip = readLine().split(' ').map{it.toInt()}
        for(j in 0 until N) cost[i][j]=ip[j]
    }
    for(i in 0 until N) {
        sol(i,i, 0, 1)
    }
    println(ans)
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/10971.cpp