자바스크립트 코딩테스트 강좌, 외판원의 순회 경로 짜기

안녕하세요! 이번 강좌에서는 코딩테스트에서 자주 출제되는 문제 중 하나인 외판원의 순회 문제(Traveling Salesman Problem, TSP)를 다루어 보겠습니다. 이 문제는 그래프와 동적 프로그래밍(Dynamic Programming)의 중요한 개념을 이해하는 데 도움이 됩니다.

1. 문제 설명

외판원의 순회 문제는 주어진 도시들 사이를 방문하며, 모든 도시를 한 번씩 방문한 후 출발 도시로 돌아오는 경로 중 최소 비용을 찾는 문제입니다. 이 문제는 일반적으로 각 도시 간의 이동 비용이 주어지는 거리 행렬로 표현되며, 외판원은 모든 도시를 반드시 한번씩 방문해야 합니다.

2. 문제의 수학적 표현

도시의 개수를 N이라고 할 때, 도시 간의 거리 행렬은 cost[i][j] 형태로 정의됩니다. 여기서 cost[i][j]는 도시 i에서 도시 j로 이동하는 비용을 나타냅니다. 외판원이 방문해야 할 경로는 다음과 같이 표현할 수 있습니다:

min(cost[0][1] + cost[1][2] + ... + cost[N-1][0])

3. 문제 해결 접근법

외판원의 순회 문제는 NP-hard 문제에 속하므로, 완전 탐색(Brute Force 방식)으로 해결하기에는 시간 복잡도가 매우 높습니다. 따라서 동적 프로그래밍(Dynamic Programming)을 사용하여 더 효율적으로 문제를 해결할 수 있습니다.

이 문제를 동적 프로그래밍 접근법으로 해결하기 위해 비트마스킹을 사용할 것입니다. 비트마스킹은 각 도시를 비트로 표현하여 방문 여부를 쉽게 체크할 수 있도록 도와줍니다. 아래의 알고리즘 단계로 문제를 접근해보겠습니다.

3.1 비트마스킹을 통한 상태 표현

방문한 도시의 상태를 비트마스크로 표현합니다. 예를 들어, 도시가 4개일 경우:

  • 0000: 아무 도시도 방문하지 않음
  • 0001: 도시 0 방문
  • 0010: 도시 1 방문
  • 0011: 도시 0과 도시 1 방문
  • …이와 같은 방식으로 모든 조합을 표현할 수 있습니다.

3.2 동적 프로그래밍 테이블 정의

DP 테이블 dp[mask][i]는 mask에 해당하는 도시들을 방문하고, 도시 i에서 출발했을 때의 최소 비용을 저장합니다. 초기 상태에서 mask는 1로 설정되어 있으며, 모든 다른 상태는 무한대(INFINITY)로 초기화합니다.

4. 알고리즘 구현

이제 우리가 작성한 알고리즘을 자바스크립트로 구현해 보겠습니다.

function tsp(cost) {
    const N = cost.length;
    const INF = Number.MAX_SAFE_INTEGER;
    const dp = new Array(1 << N).fill(null).map(() => new Array(N).fill(INF));
    
    // Starting point
    dp[1][0] = 0;

    for (let mask = 0; mask < (1 << N); mask++) {
        for (let u = 0; u < N; u++) {
            if (dp[mask][u] === INF) continue; // Skip if u is not visited

            // Visit all other cities not in the current mask
            for (let v = 0; v < N; v++) {
                if (mask & (1 << v)) continue; // Skip if v is already visited

                const nextMask = mask | (1 << v);
                dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + cost[u][v]);
            }
        }
    }

    let ans = INF;
    for (let i = 1; i < N; i++) {
        ans = Math.min(ans, dp[(1 << N) - 1][i] + cost[i][0]);
    }

    return ans;
}

5. 시간 복잡도

이 알고리즘의 시간 복잡도는 O(N^2 * 2^N)입니다. 비트마스킹을 통해 상태를 나타내는 방법과 DP 테이블 업데이트 과정이 결합되어 있기 때문에, 도시 수가 증가하면 상당한 연산 시간이 소요됩니다. 고로 이 알고리즘은 N이 20 이하일 때에만 실용적입니다.

6. 테스트 및 예제

이제 알고리즘을 테스트하기 위해 몇 가지 예제를 들어보겠습니다. 다음은 도시 간의 비용 행렬입니다:

const costMatrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
];
console.log(tsp(costMatrix)); // Expected output: 80

7. 결론

외판원의 순회 문제를 다루면서 동적 프로그래밍과 비트마스킹을 활용한 경로 탐색 기법을 이해할 수 있었습니다. 이 문제는 단순한 이동 경로 문제처럼 보일 수 있지만, 인터넷 기업의 경로 최적화 문제 등 여러 분야에 응용될 수 있는 중요한 알고리즘 문제입니다.

이번 강좌가 자바스크립트를 활용한 알고리즘 문제 해결에 도움이 되었기를 바라며, 추가적인 연습을 통하여 더 많은 문제를 풀이하시면 좋겠습니다. 감사합니다!