백준 2098 외판원 순회 - 비트마스킹,dp,dfs c++

문제 링크

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

2098번: 외판원 순회

해설 및 회고

쉽지않은 문제였다. 전날 밤 12시에 자기전에 이 문제를 처음 보고 다음날 오늘 오후에 걸려서 다 풀었다.

종만북을 이제 첨 보기 시작했는데, 2권 첫장에 나온 내용이 비트마스킹 관련된 부분이었다.

 

• 외판원 문제에 비트마스킹을 적용해야 하는 이유

외판원 문제를 푸는데 , 만약 완전탐색을 통해서 문제를 풀고자 한다면, 외판원 문제의 시간복잡도는 O(N!)이다. 

하지만 이 문제를 비트마스킹을 적용한다면 최대 N*2^N의 공간복잡도를 보장하면서, 경로가 없는 경우에는 그만큼의 경우의 수가 추가적으로 빠지게 되므로, 문제의 N=16의 범위 내에서 문제를 충분히 해결할 수 있다.

외판원이 순회를 하면서 방문한 마을의 갯수를 반드시 확인해야 하는 이유는 한번 방문한 마을을 다시 재방문 할 수 없다는 조건, 그리고 a-->b 와 b-->a의 비용이 다르다는 점 등을 비추어 보았을때, 지금까지 어디어디의 마을을 방문했다는 state는 메모이제이션에서 반드시 들어가야 하는 요소이다.

 

그 이후엔 dfs 백트래킹 방식을 적용해서 문제를 풀어내면 된다.

#include <iostream>
using namespace std;
 
const int INF = 987654321;
int N;
int W[17][17];
int dp[16][1<<16];
 
int TSP(int curr, int visited){ //현재 도시가 curr이고, curr을 포함해서 방문했었던 도시들을 표현한게 visited일때, 
//앞으로 가야할 길 중에 최소를 구하는거다.
    int result;
    int ret = dp[curr][visited];
    if(ret!=0)
        return ret; //앞으로 다 돌기까지 남은 길 중에 최솟값을 미리 구해놨다면, 그 경로가 최소임이 자명하므로, 
 //메모이제이션을 통해 저장된 값 불러옴.
    //다 돌고 처음 도시로 돌아가는 경우
    if(visited==((1<<N)-1)){
        if(W[curr][0]!=0)
            return W[curr][0];
        return INF;
    }
 
    ret=INF;
    for(int i=0; i<N;i++){
        if(W[curr][i]==0 || (visited&(1<<i))) //1. 길이 없거나, 2. 한번방문한 도시(i)를 다시 방문하려고 한다면 --> 건너뛰어야함
            continue;
        ret = min(ret,W[curr][i]+TSP(i,visited|1<<i)); // curr-->i로 간다음에 i에서 나머지 도시들 순회한거 중 최소 or 
 //지금 값. 2개중 최소를 가림
    }
    dp[curr][visited]=ret; //최소화된 값을 dp배열에 메모이제이션
    return ret;
}
 
int main(void){
    cin>>N;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin>>W[i][j];
 
    cout<<TSP(0,1);
}