[백준] 10971번: 외판원 순회 2 - Kotlin[코틀린]

문제

 

10971번: 외판원 순회 2

 

---

풀이

 

 이 문제는 Traveling Salesman problem(TSP)라고 불리는 외판원 순회 문제 유형의 가장 기본적인 형태이다.

 

 DFS로 풀이하면 된다. 한 도시에서 모든 도시를 방문했을 때, 출발지로 다시 돌아올 수 있다면 총 비용을 현재까지의 최솟값과 비교하여 저장하는 방식이다. 모든 도시를 한 번씩 출발지로 하여 dfs()를 호출하면 된다.

 

---

코드

 

import java.util.*
import kotlin.math.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val city = br.readLine().toInt()

    val cost = Array(city){ IntArray(city) }
    for(i in 0 until city) {
        val st = StringTokenizer(br.readLine())
        for(j in 0 until city) {
            cost[i][j] = st.nextToken().toInt()
        }
    }

    val visited = BooleanArray(city)
    var min  = Long.MAX_VALUE

    fun dfs(start: Int, now: Int, res: Long, depth: Int) {
        if(depth == city) { // 모든 도시 방문
            if(cost[now][start] != 0) { // 출발지와 연결된 경우
                min = min(min, res + cost[now][0])
            }
            return
        }

        for(i in 1 until city) {
            if(!visited[i] && cost[now][i] != 0) {
                visited[i] = true
                dfs(start, i, res + cost[now][i], depth+1)
                visited[i] = false
            }
        }
    }

    for(i in 0 until city) {
        visited.fill(false) // 방문 처리 배열 초기화
        visited[i] = true
        dfs(i, i, 0, 1)
    }

    bw.write("$min")
    bw.flush()
    bw.close()
    br.close()
}