[Algorithm] Baekjoon 2098번 : 외판원 순회

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

2098번: 외판원 순회

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
#define MAX_NUM 0x3f3f3f3f
 
int n = 0;
int dp[16][1 << 16];
int adjMatrix[16][16];
int targetBit;
int startVertex = 0;
 
int DFS(int curVertex, int curBit)
{
 
    if (curBit == targetBit) // 모든 도시는 방문했지만, (curBit는 순서와 상관없는 전체경로).
    {
        if (adjMatrix[curVertex][startVertex] == 0) // '현재시점'에서 출발지로 되돌아 갈 수 없다면
        {
            return MAX_NUM;
        }
        else return adjMatrix[curVertex][startVertex]; // 되돌아 갈 수 있으면 거리값 리턴.
    }
 
    if (dp[curVertex][curBit] != -1) // 갱신이 되어있는 상태에서, 다른 곳에서 dp[curVertex][curBit]값을 요청한다면 그대로 리턴시켜주면 된다.
    {
        return dp[curVertex][curBit]; 
    }
    
    // 최소값 갱신
    dp[curVertex][curBit] = MAX_NUM;
 
    for (int i = 0; i < n; ++i)
    {
        if (adjMatrix[curVertex][i] == 0) continue; // 방문할 수 없는 곳일 경우
        if ( (curBit & (1 << i) ) > 0) continue; // 현재까지 방문했던 경로중에 이미 i경로가 있는경우, 단순 방문체크라 생각
 
        dp[curVertex][curBit] = min(dp[curVertex][curBit], adjMatrix[curVertex][i] + DFS(i, curBit | (1 << i)));
    }
    
    return dp[curVertex][curBit];
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int a, b, c, d;
 
    cin >> n;
 
    targetBit = (1 << n) - 1;
    memset(dp, -1, sizeof(dp));
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> adjMatrix[i][j];
        }
    }
 
    startVertex = 0;
 
    cout << DFS(startVertex, 1 << startVertex) << endl;
}
 
 
 
 
 

 

 

모든 시작지점에 대해서 자기자신을 제외한 다른 모든 정점을 순회하고 다시 자기자신한테 왔을때의 최소비용을 구하는 문제이다.

 

당연히 완전탐색으로 하려면.. 어마어마하게 많은 수행속도가 필요하기 때문에 DP를 적용해야 한다.

모든 경우의 수를 구해서 해를 도출한다고 치면... n!인데 문제에서 n은 최대 16이니까 16!이다. (대략 20조?)

이 많은 경우를 다 하려하면 당연히 성능이 최악이다.

그렇기 때문에 중복된 계산을 최대한 배제해야 한다.

 

k를 최소비용이라 할 때, dp[현재도시][방문했던도시] = k  라는 식을 세운다.

여기서 방문했던 도시를 저장하기위해 비트마스킹을 사용한다.

비트마스킹은 비트표시로 정보를 저장하는 것인데, 현재 이문제같은 경우는 그저 특정도시를 방문 했냐,안했냐만 알면 되기 때문에 총 2가지의 정보를 저장할 수 있는 비트로 표현이 가능하다.

 

만약 01001  이라면,  0번도시와 3번도시를 방문했다는 표시이고

dp[3][01001] 이라면 현재 3번도시인데, 이전에 방문했던 도시는 1번도시밖에 없다는 표현이다.

이 표현이 의미하는 바는, '현재까지 방문했던곳을 제외하고 다른곳을 방문했을 때, 출발지점으로 되돌아가기 위한 최소비용' 이다.  

그리고 이 값을 저장하는 이유는 당연히 중복되는 계산이기 때문이다.

대충 n을 5정도로 잡고 직접 경로를 살피고 위의 dp식대로 표현해보면, 같은값들이 재사용되는걸 확인할 수 있다.

 

탐색뿌리를 일단은 끝까지 내리긴 할 텐데, 그렇게 다시 올라오다 보면은 특정 정점에서 특정정점들을 방문한 상태일 때, 최소비용들이 저장되게 된다. (자식들을 전부 뿌리내린 다음, 가져온 값들에서 최소값으로 갱신할테니까)

그러다보면 dp[3][01111] 이라는 자리에 20이라는 값이 저장된다고 가정해보자.

그럼 이는 다음과 같이 해석된다.

-> 현재 3번째 정점을 방문한상태인데, '이전에 0,1,2를 방문한 상태이면서(순서 상관없이) 현재 3번 정점을 방문한 상태'라면, '현재 정점'에서 '출발 정점'으로 가는 최소비용은 20이라는 뜻이다.

 

DP문제가 다 그렇듯이.. 글로 써진걸 머리속에 그리기가 쉽지 않다.

앞서 말했듯이 N을 5정도로 잡고 경로를 노트에다가 그려본다음 살펴보면 이해가 쉽다.

 

그리고 0번정점 하나만 재귀돌려도 정답을 구할 수 있는 이유는,

0 1 2 3 4 0  의 최소비용과  2 3 4 0 1 2  의 최소비용은 같기 때문이다. 

문제에서 반드시 순환이 있다고 했으니 어떤 정점으로 시작해도 상관없다.

실제로 다른 정점으로 돌려도 정답이 나온다.

 

=== === === === === === === === === === === === === === === === === === === === === === === === === === 

 

헷갈리지말자. 백준문제에서의 첫번째 테스트케이스를 기준으로, 정답코드를 돌렸을 경우 dp[3][1101 (13)] = 13 으로 되어있다.

즉, 현재 방문정점은 3이고, 현재를 포함해서 0,2,3번 정점을 방문한 상태이며, 이 상태에서 출발정점으로 가기위한 최소비용은 13이다... 라는 뜻이다. 

아직 1번정점을 방문 안했기 때문에 1번정점을 거쳐 출발정점(0)으로 가기위한 최소비용이 13이란 말이다.

그렇기 때문에 출발정점을 0으로했을 경우, dp[0][0001 (1)] 에 최종적인 정답이 들어가있는 것이다.

 

============================================================================================

 

간만에 다시풀었다.

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int MAX_NUM = 0x3f3f3f3f;
int costInfo[16][16] = { 0 };
int n;
int dp[16][1 << 16] = { 0 };
int target = 0;
 
int DFS(int index, int visitedBit)
{
    int& result = dp[index][visitedBit];
    
    if (visitedBit == target)
    {
        if (costInfo[index][0] == 0)
        {
            return MAX_NUM;
        }
        else return costInfo[index][0];
    }
 
    if (result != -1) return result;
 
    result = MAX_NUM;
 
    for (int i = 0; i < n; ++i)
    {
        if (costInfo[index][i] == 0) continue;
        if (visitedBit & (1 << i)) continue;
 
        result = min(result, DFS(i, visitedBit | (1 << i)) + costInfo[index][i]);
    }
    
    return result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    target = (1 << n) - 1;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> costInfo[i][j];
        }
    }
 
    memset(dp, -1, sizeof(dp));
    
    cout << DFS(0, 1);
}

 

추가적으로 유의해야할 것은, 방문을 아직 안했다는 표시를 -1로 했다는것과 모든 탐색을 마치더라도 시작점으로 못돌아갈 경우 MAX_NUM을 리턴해야 한다는 것이다.

 

보통 DP문제풀 때 관성적으로 풀다보면 방문표시 안한것도 마찬가지로 MAX_NUM으로 초기화해버리는 경우가 있는데, 그럴경우 무한재귀를 돌아버릴 가능성이 있다.

특정 탐색을 했을 때 해당 DP값이 MAX_NUM일 경우, 이게 방문을 아직 안해서 MAX_NUM인건지 아니면 이 경로는 유효하지 않다는 의미의 MAX_NUM인 건지 알 수가 없다는 것이다.

그러니 계속 해당탐색을 끊임없이 반복하는 것이다.