백준 2098번 외판원 순회 (JAVA)

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

 

TSP문제 + DP문제입니다.

TSP만 사용하면 시간초과가 나오는 문제입니다.

저는 처음에 DP를 비트마스킹해서 경로로만 해서 문제를 계속 틀렸습니다. 이때의 문제점은 해당 루트의 끝 즉, 현재 위치가 어디든 같은 DP값으로 본다는 것이였습니다. 그래서 현재 어디 점이 있는지 까지를 DP로 넣어서 문제를 해결하였습니다.

 

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_2098 {
    static int n;
    static int map[][];
    static boolean visited[];
    static int dp[][];
    static int LIMIT = 1_000_001;
    static int cal(int depth, int now,int route){
        if(dp[now][route] != 0){
            return dp[now][route];
        }

        visited[now] = true;
        if(depth == n-1 && map[now][0] != 0){
            visited[now] = false;
            return map[now][0];
        }

        int result = 0;
        int temp = 1_000_000_000;

        for(int i = 0 ; i < n ; i++){
            if(now != i && !visited[i] && map[now][i] != 0 ){
                int tempRoute = route | (1 << i);
                temp = Math.min(temp, cal(depth + 1, i,tempRoute) + map[now][i]);
            }
        }

        result += temp;
        visited[now] = false;
        dp[now][route] = result;

        return result;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        n = stoi.apply(st.nextToken());
        map = new int[n][n];
        visited = new boolean[n];
        dp = new int[n][1 << n + 1];
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 0 ; j < n ; j++){
                map[i][j] = stoi.apply(st.nextToken());
            }
        }
        System.out.println(cal(0,0, 0));
    }
}