[알고리즘] 외판원 순회 2 (백준 10971번)

10971번: 외판원 순회 2

 외판원 순회, 일명 TSP라고 불리는 문제다. 외판원은 모든 도시를 최소 비용으로, 단 한 번 방문한 도시는 다시 방문할 수 없다는 조건 하에 순회하게 된다. (마지막 도시에서 출발 도시로 돌아오는 경우 제외)

 도시를 방문하는 순서 케이스들을 찾아야 하기에 순열을 구하는 문제다. 이 경우는 N의 크기가 10 이하이기 때문에 백트랙킹으로 모든 경우를 찾을 수 있다.

 

Solution

 백트랙킹으로 순열을 구할 때와 조합을 구할 떄의 차이점은, 조합은 순서를 고려하지 않아도 되기 때문에 앞선 케이스에서 먼저 선택이 되었다면 그 뒤로는 다시 그 케이스를 선택할 일은 없다. 반면 순열은 그 뒷 순서에서 새롭게 선택이 될 수도 있기 때문에 그 점을 고려해야한다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.min

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var N = 0
lateinit var w : Array<Array<Int>>
lateinit var visited: BooleanArray
var min = Int.MAX_VALUE

fun solution() {

    N = br.readLine().toInt()
    w = Array(N, { Array(N,{0}) })

    visited = BooleanArray(N)

    for(i in 0 until N)
        br.readLine().split(" ").forEachIndexed { index, s -> w[i][index] = s.toInt() }

    backTracking(0, IntArray(N))
    bw.write(min.toString())

}

fun backTracking(depth: Int, city_permutaion: IntArray)
{
    if(depth == N)
    {
        var cost = 0

        for(i in 0 until N - 1)
        {
            //가는 길이 없는 경우 중단
            if(w[city_permutaion[i]][city_permutaion[i+1]] == 0)
                return
            cost += w[city_permutaion[i]][city_permutaion[i+1]]
        }

        //마지막 도시에서 첫 도시로 돌아오는 길이 없는 경우 중단
        if(w[city_permutaion[N-1]][city_permutaion[0]] == 0)
            return
        cost += w[city_permutaion[N-1]][city_permutaion[0]]

        min = min(min, cost)
    }
    else if(depth < N)
    {
    	//만약 조합이라면 0이 아닌, 그 전 순서에서 선택된 index + 1에서부터 시작된다.
        for(city in 0 until N)
        {
            if(!visited[city])
            {
                visited[city] = true
                city_permutaion[depth] = city
                backTracking(depth + 1, city_permutaion)
                visited[city] = false
            }
        }
    }

}




fun main() {
    solution()
    br.close()
    bw.close()
}