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

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

 

---

 

해당 문제는 이전에 풀었던 문제였음에도 불구하고, 최근 기업 코테에서 이와 비슷한 유형의 문제를 풀지 못했습니다. 

아쉬운 마음에 복습하고자 해당 문제의 풀이를 작성합니다. 

 

 

해당 문제는 백트래킹으로 구현할 시 O(16!)으로 시간초과가 발생합니다. 

이 문제는 외판원 순회라는 well-known 유형입니다. 

문제의 조건과 같이 n이 16이하일 때에는 비트마스킹 dp로 해결할 수 있습니다. 

 

dp 상태는 아래와 같이 정의합니다.

dp[i][j] : 현재 위치가 i이고, 지금까지 j 도시를 방문했을 때의 최단거리

n <= 16이기에 비트마스킹을 통해 도시 방문 경과를 j변수에 담을 수 있습니다. 

2^16 = 65536이기 때문에 배열로 충분히 선언할 수 있는 크기입니다. 

 

풀이 코드는 전형적인 비트마스킹 탑다운 dp 코드입니다. 

---

코드

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define REP(i,x,y) for(int i=x;i<=y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pldld;
typedef tuple<int,int,int> ti3;
typedef tuple<ll,ll,ll> tl3;
typedef tuple<ll,ll,ll,ll> tl4;
typedef tuple<int,int,int,int> ti4;
int dx[] = {0,0,1,-1};
int dy[] = {-1,1,0,0};
/*----------------------*/

ll n, dist[17][17];
ll dp[17][1<<17];
ll f(ll cur, ll vis){
    if(vis==(1<<n)-1){
        return dist[cur][0];
    }

    ll& ret = dp[cur][vis];
    if(ret!=-1) return ret;
    ret = 2e9;

    for(int nxt=0;nxt<n;nxt++){
        if(vis&(1<<nxt) || dist[cur][nxt]) continue;
        ret = min(ret,dist[cur][nxt] + f(nxt,vis+(1<<nxt)));
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    memset(dp,-1,sizeof(dp));

    cin>>n;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++){
        cin>>dist[i][j];
        if(dist[i][j]==0) dist[i][j]=2e9;
    }
    cout<<f(0,1);
}