백준 2098 외판원 순회 Kotlin (비트마스킹, dp,dfs)

문제 출처 : https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 비트마스킹
• 비트필드를 이용한 다이나믹 프로그래밍
• 외판원 순회 문제

풀이

일반적인 dfs를 이용한 완전 탐색으로 풀면 16!의 시간 복잡도로 시간 초과가 뜬다.

비트 마스킹과 다이나믹 프로그래밍을 이용하여 시간 복잡도를 줄였다.

우선 문제에 비트 마스킹을 적용하는 법은,

도시의 수가 4일 때, 2진법으로

0번 도시를 방문하는 경우 0001

2번 도시를 방문하는 경우 0100

2번 도시와 0번 도시를 방문하는 경우 0101

모든 도시를 방문하는 경우 1111

이런 식으로 현재 방문 상태를 체크할 수 있으며, 최대 32(10000)개의 방문 상태가 있으며,

현재 도시에서 다음 도시를 방문하는 것은 cur_state | (1<< i)로 나타낼 수 있고,

현재 도시가 시작 도시로 다시 돌아온 경우를 확인하는 것(탐색 종료 조건)은 cur_state == (1<<n)-1로 나타낼 수 있고,

다음 도시가 이미 방문한 도시인지 확인하는 것은 cur_state & (1 << i) !=0로 나타낼 수 있다.

 

모든 도시를 방문하는 경우가 곧 시작 도시 i에서 시작하여 다시 i로 돌아오는 경우를 뜻한다.

만약 2번 도시에서 시작해서 다시 2번 도시로 돌아오는 경우는, 반드시 모든 도시를 방문해야 한다.

2번 도시에서 2번 도시로 돌아오지 못한다면, 모든 도시를 방문하지 못함을 의미한다.

또한, 0 -> 1 -> 3 -> 2 -> 0 이 도시를 순회하는 최단 루트라고 할 때,

3 -> 2 -> 0 -> 1 -> 3 또한 도시를 순회하는 최단 루트이기 때문에,

임의의 한 도시를 정해 탐색을 시작하면 된다.

 

이 비트 마스킹(방문 상태)를 바탕으로 메모이제이션이 필요하다.

dp[i][j] = x

i : 현재 도시

j : 방문 상태

x : i(현재 도시)를 j(방문 상태)를 가지고(i를 a,b,c 등의 도시를 거쳐 방문했을 때)의 최소 거리

 

이제 이 dp를 갱신해나가며, 이미 dp[i][j]가 채워진 경우 이를 재활용하며 모든 도시를 방문할 때까지

dfs로 메모이제이션을 하면 된다.

 

코드

import kotlin.math.*

var n = 0
val INF = 987654321
val dp = Array(16){IntArray(1 shl 16){-1} }
fun dfs(node : Int, state : Int, endState : Int, graph : Array<IntArray>) : Int{

    //모든 도시를 방문한 경우 (종료 조건)
    if(state == endState){
        //마지막 길이 존재하는 경우 마지막 길을 더해준다.
        if(graph[node][0]!=0){
            return graph[node][0]
        }
        //마지막 길이 없는 경우 INF를 넣어주어 아래 min을 통해 제외되게 만든다
        else{
            return INF
        }
    }
    //이미 state 방문 상태로 node를 방문한 경우 재활용
    if(dp[node][state]!=-1) return dp[node][state]
    //min을 구하기 위한 전처리
    dp[node][state] = INF
    for(i in 0 until n){
        //이미 방문한 도시이거나 가는 길이 없는 도시면 패스
        if(state and (1 shl i) != 0 || graph[node][i]==0) continue
        //다음 길 누적
        dp[node][state] = min(dp[node][state],graph[node][i]+dfs(i,state or (1 shl i),endState, graph))
    }
    //정답 반환
    return dp[node][state]
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    n = br.readLine().toInt()
    var graph = Array(n){
        br.readLine().split(' ').map{it.toInt()}.toIntArray()
    }
    write("${dfs(0,1,(1 shl n) -1,graph)}")
    close()
}