2098

2098 문제풀이 - 외판원 순회 (골드1)

문제 개요

외판원 순회는 주어진 도시들을 모두 한 번씩 방문하고 출발 도시로 돌아오는 최단 경로를 찾는 문제입니다.

문제 조건

1. 모든 도시를 정확히 한 번씩 방문
2. 출발했던 도시로 돌아와야 함
3. 각 도시 간 이동 비용이 주어짐
4. 도시 간 이동 비용은 양방향이 다를 수 있음

접근방법

단순 접근법의 한계

• 모든 가능한 순열을 고려하면 시간 복잡도는 O(N!)
• N이 커질수록 계산이 기하급수적으로 증가
• N > 10인 경우 현실적으로 해결 불가능

최적화 접근: DP + 비트마스크

1. 상태 표현: 비트마스크로 방문한 도시들을 표현
   • 예: 1101(2) = 1번, 3번, 4번 도시 방문
2. 메모이제이션: 중복되는 부분 문제의 결과를 저장
3. 점화식 활용: 최적 부분 구조를 이용한 해결

구현 설계

DP 테이블 정의

dp[city][visited] = 현재 도시에서 남은 도시들을 방문하는 최소 비용

점화식

dp[city][visited] = min(
    dp[nextCity][visited | (1 << nextCity)] + cost[city][nextCity]
)

구현 단계

1. DP 배열 초기화

const dp = Array.from({ length: n }, () => new Array(1 << n).fill(-1));

• dp[현재도시][방문상태] 형태의 2차원 배열
• 방문 상태는 비트마스크로 표현 (예: 1101은 0, 2, 3번 도시 방문)
• -1로 초기화하여 아직 계산되지 않은 상태 표시

2. DFS 함수 설계

const dfs = (city, visited) => {
    // 구현부
}
dfs(0, 1); // 0번 도시부터 시작, 첫 도시 방문 표시

• city: 현재 위치한 도시의 인덱스
• visited: 지금까지 방문한 도시들의 상태(비트마스크)
• 시작 도시는 임의로 0번으로 고정 (순환 경로이므로 어느 도시에서 시작해도 무관)

3. 종료 조건 처리

if (visited === (1 << n) - 1) {
    return w[city][0] || Infinity;
}
if (dp[city][visited] !== -1) {
    return dp[city][visited];
}

• 모든 도시 방문 완료: (1 << n) - 1와 비교
• 시작 도시로 돌아갈 수 있는지 확인
• 이미 계산된 경우 메모이제이션된 값 반환

4. 다음 도시 선택 및 방문

let result = Infinity;
for (let nextCity = 0; nextCity < n; nextCity++) {
    if (visited & (1 << nextCity)) continue;  // 이미 방문한 도시 제외
    if (w[city][nextCity] === 0) continue;    // 갈 수 없는 경로 제외

    result = Math.min(
        result,
        w[city][nextCity] + dfs(nextCity, visited | (1 << nextCity))
    );
}

• 방문하지 않은 모든 도시에 대해 탐색
• 비트 연산으로 방문 여부 확인 및 갱신
• 현재까지의 최소 비용과 새로운 경로의 비용을 비교하여 갱신

5. 결과 저장 및 반환

dp[city][visited] = result;
return dp[city][visited];

• 현재 상태에서의 최소 비용을 DP 배열에 저장
• 저장된 값을 반환하여 재사용 가능하게 함

시간 복잡도

• O(n²×2ⁿ): 각 도시에서 다른 모든 도시로의 이동을 고려
• 비트마스크를 사용하여 방문 상태를 효율적으로 관리
• 메모이제이션으로 중복 계산 방지

공간 복잡도

• O(n×2ⁿ): DP 배열의 크기
• n: 도시의 개수
• 2ⁿ: 가능한 모든 방문 상태의 수