[백준]10971. 외판원 순회2

📄 링크

외판원 순회2

---

💡 문제 분석

알고리즘의 대표적인 문제입니다.
모든 도시를 방문하고 시작 지점으로 돌아 오는데 필요한 최소 비용을 구하는 문제입니다. 완전 탐색으로 모든 경로를 계산해서 최소 비용을 구하는 방법을 사용할 수 있지만, 이럴 경우 O(N!)의 시간 복잡도가 소요됩니다.
이 문제에서는 N의 최대값이 10이기 때문에 10! = 3628800으로 시간 초과가 나지 않지만, N이 12를 넘어가게 되면 약 5억으로 시간 초과가 날 것입니다.

 

그렇기 때문에 부분문제로 쪼개서 동적 계획법을 사용하기로 했습니다.
tcp(cur, visited) = 현재 방문한 도시들이 visited이고 현재 위치가 cur일 때 모든 도시를 방문하고 시작 지점으로 돌아가는데 필요한 최소 비용
이렇게 최적 부분 구조로 문제를 쪼개어 메모이제이션을 합니다.

 

공간 복잡도를 줄이기 위해 비트마스킹으로 방문 처리를 해주었습니다.
(1 << N) - 1은 N개의 도시를 모두 방문 했을 경우입니다

---

⌨️ 코드

import java.util.Arrays;
import java.util.Scanner;

public class _10971_외판원순회2 {
    static int N, INF = 987654321;
    static int[][] map;
    static int[][] cache;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        cache = new int[N][(1 << N)];
        for(int i = 0; i < N; i++) {
            Arrays.fill(cache[i], -1);
        }
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                map[i][j] = sc.nextInt();
        System.out.println(tcp(0, 1));
    }

    public static int tcp(int cur, int visited) {
        if(visited == (1 << N) - 1) {
            if(map[cur][0] != 0)
                return map[cur][0];
            else
                return INF;
        }
        int ret = cache[cur][visited];
        if(ret != -1) return ret;
        ret = INF;
        for(int i = 0; i < N; i++) {
            if((visited & (1 << i)) != 0 || map[cur][i] == 0) continue;
            ret = Math.min(ret, map[cur][i] + tcp(i, visited | (1 << i)));
        }
        return cache[cur][visited] = ret;
    }
}

---

📋 회고

• 동적 계획법
• 메모이제이션
• 비트마스킹
• 초기화 잘하자