📖 외판원 순회 (Treveling Salesman Problem)

---

• 사진이 위치하는 노드에서 출발하여 다른노드를 각각 한번씩만 방문하고 다시 자기 도시로 돌아오는 가장 짧은 경로 찾는 문제
• 음이 아닌 가중치가 있는 방향성 그래프 대상

◾ DP 기반 접근

• 시간 복잡도 : O(n^2 * 2^n)
• 공간 복잡도 : O(n^2^n)

◾ 비트마스크를 이용한 집합 표현

• 이미 방문했던 도시를 재방문하면 안되니까 체크 필요
• 방문상태는 하나의 integer 변수로 표현하고 비트마스크의 shift연산과 OR 연산을 이용해서 표현

💬 알고리즘 구현

---

static int[][] arr = new int[n][n];
static int[][] dp = new int[n][(1 << n) - 1];

	private static int tsp(int node, int visit){
        // 모든 지점을 방문한 경우
        if(visit == (1 << n) - 1){
            if(arr[node][0] == 0) return INF;
            return arr[node][0];
        }

        // 이미 계산 했던 경우
        if(dp[node][visit] != INF)
            return dp[node][visit];

        for(int i = 0 ; i < n; i++){
            int next = visit | (1 << i);
            // i번 노드에 대해서 길이 없거나 방문한 경우
            if(arr[node][i] == 0 || (visit & (1 << i)) != 0) continue;

            dp[node][visit] = Math.min(dp[node][visit], tsp(i, next) + arr[node][i]);
        }

        return dp[node][visit];
	}