글 읽기 - 외판원 순회문제 시간복잡도가 궁금합니다

quki 7년 전 0

외판원 순회문제를 DP + 비트마스크로 풀었습니다.

이차원 배열 dp[i][visited] 를 잡고 i정점에서 지나온 경로가 visited(비트) 일때 최단 경로 값을 Top-down 방식으로 배열에 메모이제이션해주고 있습니다.

이때 시간 복잡도가 어떻게 나오는지 궁금합니다.

제 생각에는 dp 이차원 배열에서 전체 칸 수 x 한칸을 채우는 복잡도 = n*2^n x n(???????) = n^2*2^n 인 것 같은데 맞나요?

이차원 배열 전체를 채우는 복잡도는 알겠는데 한칸을 채우는 복잡도가 n이 맞는지 궁금합니다.

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static int[][] W;
    public static int[][] dp;
    public static int N;
    public static final int INF = 1000000000;
    /**
     * 
     * @param start 시작점
     * @param visited 현재까지 경로
     * @return
     */
    public static int getShortestPath(int current, int visited) {
         
        // 모든 정점을 다 들른 경우
        if (visited == (1 << N) - 1)
            return W[current][1];
 
        // 이미 들렸던 경로이므로 바로 return
        if (dp[current][visited] >= 0)
            return dp[current][visited];
 
        int ret = INF;
 
        // 집합에서 다음에 올 원소를 고르자!
        for (int i = 1; i <= N; i++) {
            int next = i;
 
            if ((visited & (1 << (next - 1))) != 0) 
                continue;
             
            if(W[current][next] == 0) // 0은 경로가 없으므로 pass
                continue;
             
            int temp = W[current][next] + getShortestPath(next, visited + (1 << (next - 1)));
            ret = Math.min(ret, temp);
        }
 
        return dp[current][visited] = ret;
 
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        W = new int[N + 1][N + 1];
        dp = new int[N + 1][1 << N];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                W[i][j] = sc.nextInt();
            }
        }
        // 2차원 배열의 모든 원소를 -1로
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dp[i], -1);
        }
         
        int start = 1;
        System.out.println(getShortestPath(start, 1));
 
    }
 
}

hihihi 7년 전 1

O(n^2*2^n) 맞습니당

quki 7년 전 0

감사합니당!^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

외판원 순회문제 시간복잡도가 궁금합니다

quki 7년 전 0

hihihi 7년 전 1

quki 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말