문제 설명
여행을 계획할 때, 우리는 여러 도시를 방문하고, 각 도시 사이를 이동하는데 필요한 시간과 비용을 고려해야 합니다. 아래와 같은 정보를 기반으로 최적의 여행 계획을 세우는 문제를 풀어보겠습니다.
문제: 여행 경로 최적화
당신은 N개의 도시와 각 도시 간의 이동 시간/비용을 나타낸 그래프가 주어집니다. 시작 도시에서 출발하여 모든 도시를 최소한의 시간 또는 비용으로 방문한 뒤 다시 시작 도시로 돌아오는 최적의 경로를 계산하는 프로그램을 작성하세요.
입력
- 첫 번째 줄에 도시의 개수 N (1 ≤ N ≤ 12) 가 주어집니다.
- 다음 N x N 크기의 행렬이 주어지며, 각 행렬 원소는 두 도시 간의 이동 시간(또는 비용)을 나타냅니다. 이동할 수 없는 경우는 모두 -1로 주어집니다.
출력
최소 이동 시간(또는 비용)을 출력합니다.
예제
4
0 10 15 20
10 0 -1 25
15 -1 0 30
20 25 30 0
출력:
75
문제 풀이 과정
1. 문제 이해하기
이 문제는 주어진 도시들 사이의 이동 시간을 최소화하는 경로를 찾는 문제입니다. 이는 일반적으로 외판원 문제(TSP, Traveling Salesman Problem)라고 불리며, NP-hard 문제입니다. 입력으로 주어진 그래프는 인접 행렬로 표현되어 있으며, 우리는 이 행렬을 바탕으로 최적의 경로를 탐색해야 합니다.
2. 접근 방법
이 문제를 해결하기 위해 DFS(Depth First Search)와 비트 마스킹을 사용한 동적 프로그래밍(DP) 기법을 결합할 것입니다. 비트 마스킹을 이용하면 현재 방문한 도시의 상태를 효율적으로 표현할 수 있고, 이를 통해 중복 계산을 피할 수 있습니다.
3. 코틀린 구현
fun findMinCost(graph: Array, visited: Int, pos: Int, n: Int, memo: Array): Int {
// 모든 도시를 방문한 경우
if (visited == (1 shl n) - 1) {
return graph[pos][0] // 시작 도시로 돌아가면
}
// 메모이제이션 체크
if (memo[visited][pos] != -1) {
return memo[visited][pos]
}
var ans = Int.MAX_VALUE
// 모든 도시 탐색
for (city in 0 until n) {
// 방문하지 않았고 이동 가능하다면
if ((visited and (1 shl city)) == 0 && graph[pos][city] != -1) {
val newCost = graph[pos][city] + findMinCost(graph, visited or (1 shl city), city, n, memo)
ans = Math.min(ans, newCost)
}
}
// 메모이제이션 저장
memo[visited][pos] = ans
return ans
}
fun tsp(graph: Array, n: Int): Int {
// 초기화
val memo = Array(1 shl n) { IntArray(n) { -1 } }
return findMinCost(graph, 1, 0, n, memo)
}
fun main() {
val graph = arrayOf(
intArrayOf(0, 10, 15, 20),
intArrayOf(10, 0, -1, 25),
intArrayOf(15, -1, 0, 30),
intArrayOf(20, 25, 30, 0)
)
val n = graph.size
val result = tsp(graph, n)
println("최소 이동 비용: $result")
}
4. 코드 설명
위 코드는 여행 경로를 최적화하는 알고리즘의 전체적인 흐름을 보여줍니다. 주요 부분은 다음과 같습니다:
- findMinCost: 현재 도시와 방문한 도시의 상태를 파라미터로 받아 최소 비용을 재귀적으로 계산합니다.
- tsp: 비트 마스킹과 메모이제이션을 통해 전반적인 최소 비용을 계산합니다.
5. 성능 분석
이 코드는 도시의 개수가 N일 때 O(N^2 * 2^N)의 시간 복잡도를 가지며, 이는 모든 경로를 탐색하는 DFS의 성격과 비트 마스킹으로 방문 상태를 저장하는 특성 덕분입니다. 도시의 수가 12 이하인 범위 내에서는 실제로 실행 가능하므로, 이 문제는 적당한 크기의 입력에 대해서는 효율적으로 수행할 수 있습니다.
결론
여행 계획 짜기 알고리즘 문제를 통해 DFS와 비트 마스킹을 활용한 동적 프로그래밍 기법의 어떻게 활용할 수 있는지를 알아보았습니다. 실제 코딩 테스트 및 알고리즘 문제에서 유용하게 적용할 수 있는 기술이므로, 꼭 마스터하시기 바랍니다. 앞으로도 다양한 문제를 통해 알고리즘 능력을 지속적으로 향상시키세요!