[백준][KOTLIN][10971]외판원 순회2

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

10971번: 외판원 순회 2

문제 풀이

1. 첫번째 도시 부터 N 번째 도시까지 하나씩 출발 도시로 선택한다.

2. dfs 를 이용하여 순회여행 경비의 최소값을 찾는다.

2-1. dfs 인자로 N(도시의 개수), VISIT(방문 도시 여부), W(도시 이동 비용), depth(방문한 도시 개수), sum(현재까지의 비용 총합) 넘겨 준다.

2-2. 1번 탐색 시 출발도시를 first 변수에 저장한다.

2-3. tspResult 값을 Int.MAX_VALUE 로 초기 설정 한다.

3. dfs 로 탐색하여 나온 결과 중 최소값을 찾는다. 이때 dfs 과정에서 W[start][[i] 가 0 인 경우 도로가 연결되지 않은 도시이므로 방문하지 않는다.

코드

import java.io.*

var tspResult = Int.MAX_VALUE
var first = 0

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val W = Array(N + 1) {
        IntArray(N + 1) {
            0
        }
    }
    val visit = BooleanArray(N + 1) {
        false
    }

    repeat(N) {
        val arr = br.readLine().split(" ").map { it.toInt() }.toIntArray()

        arr.forEachIndexed { index, a ->
            W[it + 1][index + 1] = a
        }
    }

    visit[0] = true

    for (i in 1..N) {
        first = i
        visit[i] = true
        dfs(N, i, W, visit, 1, 0)
    }


    println(tspResult)
}

fun dfs(n: Int, start: Int, w: Array<IntArray>, visit: BooleanArray, depth: Int, sum: Int) {
    if (depth >= n && w[start][first] != 0) {
        //println("${w[start][first]}, $tspResult")
        tspResult = Math.min(tspResult, sum + w[start][first])
        return
    }

    for (i in 1..n) {
        if (!visit[i]) {
            //println("start $start, i $i, sum $sum depth $depth")
            visit[i] = true
            if (w[start][i] != 0) {
                dfs(n, i, w, visit, depth + 1, sum + w[start][i])
            }
            visit[i] = false
        }
    }
}