코틀린 코딩테스트 강좌, 세일즈맨의 고민

문제 설명

세일즈맨이 여러 도시를 돌며 고객을 방문해야 합니다. 세일즈맨은 각 도시에서 상품을 판매할 수 있으며, 각 도시는 서로 다른 거리에 위치하고 있습니다. 세일즈맨의 목표는 모든 도시를 순회하여 처음 출발한 도시로 돌아오는 최소의 비용을 계산하는 것입니다. 이 문제는 유명한 “외판원 문제(Traveling Salesman Problem, TSP)”로 알려져 있으며, NP-완전 문제 중 하나입니다.

문제 설명을 위한 예시

다음과 같이 4개의 도시가 있다고 가정해 보겠습니다:

도시 A – (0, 0)
도시 B – (1, 2)
도시 C – (4, 3)
도시 D – (7, 7)

이 경우 세일즈맨은 A, B, C, D 도시를 모두 방문하고 다시 A로 돌아오는 최소 경로의 거리를 찾아야 합니다.

문제 접근 방법

이 문제를 해결하기 위해 여러 접근 방식이 있지만, 주로 사용하는 방법은 동적 프로그래밍(Dynamic Programming)입니다. 동적 프로그래밍을 사용하여 모든 도시를 탐색하는 것을 최적화할 수 있습니다.

1. 비트 마스킹을 이용한 동적 프로그래밍

비트 마스킹을 사용하면 각 도시의 방문 여부를 비트로 표현할 수 있습니다. 예를 들어, 4개의 도시에 대한 비트 표현은 0000(아무 도시도 방문하지 않음)부터 1111(모든 도시를 방문함)까지의 값으로 표현될 수 있습니다. 각 비트의 1은 해당 도시가 방문되었음을 의미합니다.

2. 동적 프로그래밍 상태 정의

DP 테이블을 정의합시다. dp[mask][i]는 방문한 도시를 나타내는 비트 마스크가 mask일 때 도시 i에 도착하기 위한 최소 비용을 의미합니다. 초기 상태는 dp[1<

3. 점화식 정의

점화식은 다음과 같습니다:

dp[mask][i] = min(dp[mask ^ (1 << i)][j] + dist[j][i]) for all j where j is in mask and j != i

이 점화식은 현재 도시 i에서 비트 마스크가 mask인 상태에서 이전에 방문한 도시 j에서 오는 최적 비용을 계산하는 과정입니다.

코드 구현

알고리즘을 코틀린으로 구현해 보겠습니다.

        
        fun main() {
            val cities = arrayOf(
                Pair(0, 0),
                Pair(1, 2),
                Pair(4, 3),
                Pair(7, 7)
            )
            val n = cities.size
            val dist = Array(n) { IntArray(n) }
            
            // 거리 계산
            for (i in 0 until n) {
                for (j in 0 until n) {
                    dist[i][j] = manhattanDistance(cities[i], cities[j])
                }
            }

            // DP 배열 초기화
            val dp = Array(1 shl n) { IntArray(n) { Int.MAX_VALUE } }

            for (i in 0 until n) {
                dp[1 shl i][i] = 0
            }

            // DP 처리
            for (mask in 1 until (1 shl n)) {
                for (i in 0 until n) {
                    if (mask and (1 shl i) == 0) continue
                    for (j in 0 until n) {
                        if (mask and (1 shl j) == 0 || i == j) continue
                        dp[mask][i] = minOf(dp[mask][i], dp[mask xor (1 shl i)][j] + dist[j][i])
                    }
                }
            }

            // 최소 비용 계산
            var minCost = Int.MAX_VALUE
            
            for (i in 0 until n) {
                minCost = minOf(minCost, dp[(1 shl n) - 1][i] + dist[i][0])
            }
            println("최소 비용: $minCost")
        }

        fun manhattanDistance(city1: Pair, city2: Pair): Int {
            return Math.abs(city1.first - city2.first) + Math.abs(city1.second - city2.second)
        }

코드 설명

위의 코드는 다음과 같은 과정을 거쳐 동적 프로그래밍을 통해 최적 경로의 비용을 계산합니다:

거리 계산: 두 도시 간의 맨해튼 거리를 계산합니다.
DP 초기화: 모든 도시를 방문하지 않은 상태에서의 초기 DP 배열을 설정합니다.
DP 처리: 비트 마스크와 현재 도시를 기반으로 최적 비용을 계산합니다.
최소 비용 계산: 모든 도시를 방문한 후 돌아올 때의 최소 비용을 계산합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n^2 * 2^n)입니다. 이는 n이 작을 때 유효하게 작동하지만, n이 커질수록 성능 저하가 급격히 발생합니다. 따라서, 이 문제는 대규모 입력에서는 비효율적일 수 있어, 다양한 최적화 기법이 필요할 수 있습니다.

결론

“세일즈맨의 고민” 문제는 코딩 테스트에서 자주 등장하는 알고리즘 문제 중 하나입니다. 이 문제를 통해 동적 프로그래밍 및 비트 마스킹의 중요성을 이해하고 실제로 코틀린을 사용하여 해결하는 방법을 배울 수 있습니다. 최적화 및 기타 기법에 대해 깊이 있는 추가 학습을 통해 더 복잡한 문제를 해결할 수 있는 능력을 키우는 것이 좋습니다.