스위프트 코딩테스트 강좌, 외판원의 순회 경로 짜기

문제 정의

외판원 문제(Travelling Salesman Problem, TSP)는 n개의 도시와 각 도시 간의 거리가 주어졌을 때, 외판원이 모든 도시를 한 번씩 방문하고 다시 출발 도시로 돌아오는 최소 경로의 길이를 구하는 문제입니다. 입력으로는 도시의 수 n과 각 도시 간의 거리 행렬이 주어집니다.

입력 형식

• 첫 번째 줄: 도시의 수 n (1 ≤ n ≤ 10)
• 이후 n개의 줄: 거리 행렬, i번째 줄에는 i번째 도시와 각 도시 간의 거리가 주어짐 (A[i][j]는 도시 i에서 j까지의 거리)

출력 형식

모든 도시를 방문하고 다시 시작 도시로 돌아오는 최소 경로의 길이를 출력합니다.

문제 풀이 접근법

이 문제는 NP-Hard 문제에 속하기 때문에, 가지치기를 통한 동적 프로그래밍 기법을 사용하여 해결할 수 있습니다. 이 방법을 통해 모든 가능한 경로를 탐색하는 것이 아니라, 경로를 만들면서 가장 비용이 적은 경로만을 선택하게 됩니다.

1단계: 데이터 구조 설계

우선 도시의 거리 정보를 저장할 거리 행렬을 2차원 배열로 선언합니다. 또한 각각의 도시를 방문했는지를 체크할 배열 및 현재까지의 총 거리 값을 저장할 변수를 선언합니다.

2단계: 비트마스크와 재귀 함수 사용하기

각 도시를 방문했는지를 비트마스크를 통해 나타냅니다. 재귀 함수를 통해 다음 도시로 이동할 때마다 방문한 도시를 체크하고, 최종적으로 모든 도시를 방문한 후 다시 시작 도시로 돌아오는 경로의 거리를 계산합니다. 방문한 도시는 비트마스크를 통해 쉽게 표현할 수 있기 때문에 효율적으로 처리할 수 있습니다.

3단계: 최적 경로 찾기

모든 가능한 경로를 탐색할 필요 없이, 현재 선택된 경로 중에서 최소 거리를 계산하는 방식으로 진행합니다. 만약 주어진 경로가 최종적으로 모든 도시를 방문한 경우, 이전 거리와 비교하여 최솟값을 갱신합니다.

스위프트 코드 구현

아래는 스위프트를 이용한 외판원의 순회 경로를 찾는 코드입니다.

let INF = Int.max
var dist: [[Int]] = []
var n = 0
var dp: [[Int]] = []
var visited: Int = 0
var ans: Int = INF

func tsp(pos: Int, visited: Int) -> Int {
    if visited == (1 << n) - 1 {
        return dist[pos][0] != 0 ? dist[pos][0] : INF
    }
    
    if dp[pos][visited] != -1 {
        return dp[pos][visited]
    }
    
    var minimum = INF
    for city in 0.. Int {
    visited = 1 // start from city 0
    dp = Array(repeating: Array(repeating: -1, count: 1 << n), count: n)
    let minimumDistance = tsp(pos: 0, visited: visited)
    return minimumDistance
}

// 거리 행렬 예시
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
n = dist.count

let result = findMinimumRoute()
print("최소 경로의 길이는 \(result)입니다.")
            

코드 분석 및 동작 원리

이 코드는 비트마스크를 활용하여 방문 완료 여부를 체크하고, 재귀적으로 가능한 경로를 탐색하여 최소 경로를 계산합니다. 각 도시를 방문할 때마다 총 거리를 업데이트하고, 모든 도시를 방문한 후 최종적으로 시작 도시로 돌아오는 경로의 거리를 반환합니다.

1. dp 배열 초기화

dp 배열은 각 도시와 방문 상태에 따른 최소 경로 거리를 저장합니다. 처음에는 모든 요소를 -1로 초기화하여 방문하지 않은 상태로 설정합니다.

2. 재귀 함수 tsp()

재귀 함수 tsp()는 현재 위치(pos)와 방문한 도시 비트마스크(visited)를 인자로 받아 최적 경로를 계산합니다. 만약 모든 도시를 방문한 경우, 시작 도시로 돌아가는 경로를 비용과 비교하여 최소값을 반환합니다.

3. 경로 계산

비트마스크를 통해 아직 방문하지 않은 도시를 체크하고, 다음 도시로의 이동을 계산하는 방식으로 모든 가능성을 탐색합니다. 각 도시 간의 거리에서 `tsp()`를 호출하여 전체 경로 거리를 누적합니다.

결론

이번 강좌에서는 외판원의 순회 문제에 대해 자세히 알아보았습니다. 비트마스크와 DP를 활용하여 효율적으로 해결할 수 있는 방법에 대해 논의했고, 스위프트 코드를 직접 작성해보았습니다. 코딩 테스트에서 자주 나오는 이 문제를 통해 알고리즘 문제 해결능력을 한층 더 키우기를 바랍니다.

여러분의 코딩 여정에 도움이 되길 바랍니다! 감사합니다.