안녕하세요, 여러분! 이번 강좌에서는 외판원의 순회 문제(TSP, Traveling Salesman Problem)를 해결하는 알고리즘을 구현하는 방법에 대해 자세히 알아보겠습니다. TSP는 주어진 도시를 최소 비용으로 모두 순회한 후, 다시 시작했던 도시에 돌아오는 경로를 찾는 문제입니다. 이 문제는 고전적인 조합 최적화 문제 중 하나로, 여러 가지 접근 방법이 있습니다.
1. 문제 설명
주어진 N개의 도시가 있고, 각 도시 간의 이동 비용이 주어졌을 때, 모든 도시를 한 번씩 방문하고 시작한 도시로 돌아오는 최소 비용 경로를 구하는 것이 목표입니다. 이 문제를 해결하기 위해 다음과 같은 입출력 형식을 사용합니다.
입력
- 첫째 줄에는 도시의 개수 N (1 ≤ N ≤ 10)이 주어집니다.
- 둘째 줄부터 N개의 줄에 걸쳐 N x N 크기의 인접 행렬이 주어지며, 인접 행렬의 i행 j열의 값은 도시 i에서 도시 j로 가는 비용을 나타냅니다. 만약 두 도시 간의 이동이 불가능하다면, 그 비용은 0입니다.
출력
- 모든 도시를 방문하고 다시 시작 도시로 돌아오는 최소 비용을 출력합니다.
2. 문제 해결 과정
문제를 해결하기 위해 다양한 알고리즘이 존재하지만, 여기서는 DFS(Depth-First Search)와 메모이제이션(Memoization) 기법을 사용한 접근 방식을 설명하겠습니다. 다음은 문제를 해결하는 단계입니다.
Step 1: 문제 이해하기
TSP 문제를 해결하기 위해서는 모든 가능한 경로를 찾아야 합니다. 완전 탐색을 통해 모든 경우의 수를 따져 최소 비용을 계산할 수 있지만, 도시의 수가 증가할수록 경우의 수는 기하급수적으로 증가하므로 효율적인 방법이 필요합니다.
Step 2: 비트 마스크로 방문 도시 기록하기
비트 마스크를 사용하여 각 도시의 방문 여부를 기록할 수 있습니다. 예를 들어, 4개의 도시가 있을 경우, 각 도시를 비트로 표현하여 0b0000에서 0b1111까지의 경우를 만들 수 있습니다. 이 방법을 통해 각 도시를 방문했는지 여부를 간편하게 확인할 수 있습니다.
Step 3: DFS 및 메모이제이션 구현하기
DFS를 이용하여 모든 경로를 탐색하면서 비용을 계산하되, 이미 계산한 경로는 저장하여 중복 계산을 피하는 메모이즈 기법을 활용합니다. 아래는 이를 구현한 파이썬 코드입니다:
from sys import maxsize
def tsp(curr_city, visited, n, cost_matrix, memo):
if visited == (1 << n) - 1: # All cities visited
return cost_matrix[curr_city][0] or maxsize # Return to starting city or maxsize if not possible
if memo[curr_city][visited] != -1:
return memo[curr_city][visited] # Return already computed cost
min_cost = maxsize
for city in range(n):
if visited & (1 << city) == 0: # City not visited
new_cost = cost_matrix[curr_city][city] + tsp(city, visited | (1 << city), n, cost_matrix, memo)
min_cost = min(min_cost, new_cost)
memo[curr_city][visited] = min_cost
return min_cost
def solve_tsp(n, cost_matrix):
memo = [[-1] * (1 << n) for _ in range(n)]
return tsp(0, 1, n, cost_matrix, memo) # Start from city 0 with only city 0 visited
# Example usage
if __name__ == "__main__":
n = 4 # Number of cities
cost_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
result = solve_tsp(n, cost_matrix)
print(f"Minimum cost: {result}")
Step 4: 코드 설명
위 코드는 다음과 같은 주요 함수로 구성됩니다:
tsp(curr_city, visited, n, cost_matrix, memo): 현재 도시, 방문한 도시의 비트마스크, 도시의 수, 비용 행렬, 그리고 메모이제이션을 위한 리스트를 매개변수로 받아, 최소 비용을 계산합니다.solve_tsp(n, cost_matrix): 메모이제이션 리스트를 초기화하고 TSP 기능을 수행합니다.
Step 5: 시간 복잡도 분석
위 알고리즘의 시간 복잡도는 O(n^2 * 2^n)입니다. 여기서 n은 도시의 개수, 2^n는 모든 비트마스크 조합의 수입니다. 따라서 도시의 개수가 많아질수록 계산량이 급격히 증가할 수 있으므로, 실제 문제에서는 도시 개수를 10개 이하로 제한합니다.
3. 결론
이번 강좌에서는 외판원의 순회 문제(TSP)에 대한 개념 및 알고리즘 구현 방법에 대해 알아보았습니다. TSP 문제는 다양한 문제 해결 기법을 활용할 수 있는 좋은 예제이며, 깊은 이해를 통해 다른 알고리즘 문제에도 적용할 수 있는 사고를 기르는데 도움이 됩니다.
코딩 테스트에서 TSP와 관련된 문제를 만나게 될 경우, 위와 같은 방식으로 접근해 보시면 좋을 것입니다. 이제 여러분이 이 문제를 독립적으로 해결할 수 있도록 더욱 연습하시기 바랍니다. 감사합니다!