[BOJ] 2098 외판원순회 C++

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

2098번: 외판원 순회

코딩하는 사람이라면 반드시 풀어야 하는 외판원 순회 문제!

브루트포스에서 봤을 때는 귀욤귀욤한 문제였는데 골1 수준으로 오니깐 알고리즘이 너무 어려워졌다...

브루트 포스를 했을 때는 그냥 모든 정점에서 DFS를 하고 최솟값을 출력하면 되었지만 그렇게 풀게 되면  이번 문제에서는 시간제한이 1초밖에 되지 않기 때문에 비트마스킹과 동적 프로그래밍을 이용해야 풀 수 있다.

 

그럼 어떻게 풀어야 할까?

일단 최대 도시의 수가 16개이므로 모든 경로는 (1<<16)-1가지 이기 때문에 비트를 이용하여 표현이 가능하다.

도시가 4개인 경우 모든 경로를 이진수로 나타내보았다

외판원순회 문제는 결국 사이클이 존재 한다는 것이다. 만약 비용이 최소인 경우가 0->3->1->4->2->5->6->0 이고 이것을 알고 있다고 가정해보자. 그렇다면 0->1->3->4와 같은 경우는 4에 방문했을 때 끝까지 가보지 않더라도  2->5->6->0이 최소 경로 인 것을 알기 때문에 더 방문 할 필요가 없다.

위를 활용하여 now를 현재 도시 visit을 경로라고 dfs를 돌면서 dp[now][visit]에 최소 비용만 넣어주면 된다. dp[now][visit]이 이미 존재 한다면 굳이 dfs를 돌지 않고 바로 return해주면 된다. 쉽게 말해 dp[now][visit]에는 visit을 제외한 나머지 경로의 최솟값이 저장된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#define MAX 16000001 // 비용이 최대 1000000이고 도시가 16개이므로 최대 비용은 16000000 이하이다
using namespace std;
int N;
int dp[16][1<<16]; //최대 도시 갯수가 16개이므로
int weight[16][16];
int DFS(int now, int visit){
    if(dp[now][visit]!=-1){
        return dp[now][visit];
    }
    if(visit==(1<<N)-1){
        //방문하는 마지막점이 0과 연결되지 않으면 불가능하단 의미로 MAX를 리턴해준다
        if(weight[now][0]==0) return MAX;
        return weight[now][0];
    }
    dp[now][visit]=MAX;
    for(int i=0;i<N;i++){
        //이미 방문한 곳이거나 연결되있지 않다면 continue
        if(visit&(1<<i)||weight[now][i]==0) continue;
        //dp[now][visit]에는 visit을 제외한 나머지 경로의 최솟값이 저장된다.
        dp[now][visit]=min(dp[now][visit],DFS(i,visit|(1<<i))+weight[now][i]);
    }
    return dp[now][visit];
}

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) cin>>weight[i][j];
    }
    fill(&dp[0][0],&dp[15][1<<16],-1);
    cout<<DFS(0,1);
    return 0;
}