[백준] 외판원 순회(2098)

문제 링크 : [백준] 외판원 순회(2098)

문제 설명

n개의 도시가 있고, 외판원이 한 도시에서 시작해서 그 도시까지 돌아오는데 최소비용으로 돌아오는 비용을 출력합니다. 아무도시에서나 시작할 수 있고, 도로는 단방향입니다.

입력

N(도시의 수, 2<=N<=16)
도시간 비용이 인접행렬로 주어집니다.(각 비용은 1,000,000 이하의 양의 정수)

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

출력

원래 순열

35

카테고리

#DP

시간 복잡도 상한

O(N!)이하면 왠만하면 됩니다.

해결 방법

1. 모든 경우를 순서대로 구하면 답은 나오나 N!의 시간복잡도가 나와서 TLE가 됩니다.
2. 먼저 시작점이 중요하지 않다는 사실을 인지해야합니다.
   2-1. 모든 경우는 싸이클이 이루어지기 때문에 지나가는 도시 순서가 같다면 어디서 시작하든 비용이 같습니다.
   2-2. 그렇기 때문에 시작점은 아무데나 잡아도 되고, 개발자 특성상 제일 낮은 번호인 0번에서 직한다고 보면 됩니다.
3. 무식하게 푸는 방법으로 생각해보면, 현재의 위치와 어떤 도시를 방문했는지만 가지고 재귀로 풀 수 있습니다.
   3-1. 어떤 도시를 방문했는지는 비트 연산으로 int 범위의 변수 하나로 저장할 수 있습니다.
   3-2. i번 도시를 방문했다면 2ⁱ 비트를 1로 변경하여 방문여부를 저장 할 수 있습니다.
   3-3. 기존 도시 방문 상태에 or 연산을 통하여 계속 방문한 곳들을 저장하며 재귀를 호출 할 수 있습니다.
4. 기저 조건은 모든 도시를 방문했을 때, 현재 도시에서 0번 도시로 가는 비용을 반환하면 됩니다.
   4-1. 모든 도시를 방문했는지는 현재 도시 방문 상태 변수가 2ⁿ-1 이면 모든 도시를 방문했다고 볼 수 있습니다.
5. 재귀 몇 단계를 돌려보면 호출관계에서 중복이 많이 발생하는 것을 알 수 있습니다.
6. 따라서 재귀함수 앞에 캐시처럼 DP 배열을 관리하면 시간복잡도 안에서 해결 할 수 있습니다.
7. 복잡하고 어려운 DP의 경우, 아래의 내용을 파악하고 점화식을 세워야 합니다.
   7-1. 부분 문제로 분할
   7-2. 분할한 부분문제들의 답을 가지고, 현재 문제를 풀 수 있는지
8. 하지만 이런 방식으로 DP를 해결할 수도 있습니다.

시간복잡도

O(N*2^N)

코드

#include<cstdio>
#include<algorithm>
#define M 99999999
using namespace std;
int n,d[16][16],e[16][1<<16],i,j,a=M,f;
int r(int s,int p){
    if(p==f)return d[s][0];
    if(e[s][p])return e[s][p];
    e[s][p]=M;
    for(int i=0;i<n;i++)if(!(p&(1<<i)))e[s][p]=min(e[s][p],r(i,p|(1<<i))+d[s][i]);
    return e[s][p];
}
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++)for(f|=1<<i,j=0;j<n;j++){
        scanf("%d",d[i]+j);if(i!=j&&!d[i][j])d[i][j]=M;
    }
    printf("%d",r(0,1));
}