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

백준의 외판원 순회(2098) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 도시의 갯수가 주어졌을 때, 임의의 한 도시에서 시작해서 모든 도시를 거쳐서 다시 시작 도시로 돌아올 때 드는

   최소비용을 구해야 하는 문제이다.

   단순하게 완전탐색으로 문제에 접근하게 될 경우, 모든 도시를 줄을 세워서 최소비용을 구하는 방법이 있는데, 이 경우

   최악의 경우 16! 만큼의 연산을 필요로 하기 때문에, 시간내에 문제를 해결할 수 없다.

   따라서 본인은 메모이제이션과 비트마스크를 이용해서 구현하였다.

   여기서 비트마스크를 이용한 이유는 '상태를 저장하기 위함' 이다. '상태'라는 것은 어느 도시를 거쳤는지를 나타내는

   것이다. 예를 들어서 0번 ~ 4번 까지 총 5개의 도시가 있다고 가정해보자.

   이 때, 0번 도시를 거쳤다 라는 것은 비트마스크로 00001 로 표현할 수가 있다.

   이 후, 1번 도시를 거치게 된다면 이는 00011 로 표현할 수가 있다. 이 후에 예를 들어 4번 도시를 거쳤다 라고 가정하면

   10011로 표현을 할 수가 있다. 이 처럼, "현재까지 어느 도시들을 거쳤는지 판단"을 비트마스크로 해 주었다.

   결과적으로 모든 도시를 다 방문하게 되면 비트가 '11111'로 표현될 것이다.

   이 값은 (1 << N) - 1 로 나타낼 수 있다. 위의 예시를 그대로 가져와서 설명해보면, 5개의 도시가 있고, 모든 도시를

   다 방문하게 되면 '11111'로 나타낼 수 있다고 했다. '11111'은 십진수로 31인데, 이 값은 (1 << N = 32) - 1 한 값과

   동일하기 때문에, 모든 도시를 다 방문했다 라는 것은 비트의 상태가 (1 << N) - 1 한 값과 동일하다는 것을 의미한다.

2) 본인은 이 문제를 DFS + DP로 구현해 보았는데, 이를 위해 사용한 변수가 있다.

   바로, Cost[][] 라는 2차원 int형 배열이다. Cost[a][b] 에서, a = 현재 정점 을 의미하고, b = 현재의 상태 를

   의미한다.

   예를 들어서 Cost[1][00010] = c 라면, 이는 "현재 1번 정점이고, 현재 방문 상태는 1번 도시 한 개만 방문을 한 상태일 때,

   지금까지 든 비용의 최소비용은 c원입니다" 를 의미한다.

   즉, 각 정점에서 나올 수 있는 모든 상태의 비용들을 비교해가면서 가장 최소 비용을 찾는 것이다.

   따라서, 본인은 DFS 함수의 매개변수에 ( 현재정점 , 현재 방문한 도시의 상태를 나타내는 비트 ) 이렇게 2개의 매개변수

   를 호출해 주었다.

 

   또한, DFS함수를 가장 초기에 호출할 때 ,모든 정점에서 호출할 필요가 없다. 단순히 0번 정점에서 한번만 호출을 하더라도

   정답을 구할 수가 있다.

   그 이유는 다음과 같은 상황을 보자.

   예를 들어서 0 ~ 4번 총 5개의 도시가 존재하고, 이 도시를 순회하는 최소 비용이 드는 루트가

   0 → 1 → 2 → 3 → 4 → 0 이라고 가정해보자. 이 때, 'A원' 이라는 비용이 들었다고 가정해보면,

   2 → 3 → 4 → 0 → 1 → 2 의 최소비용은 얼마일까? 당연히 'A원' 일 것이다.

   그럼, "0번 정점에서 시작한다고 하더라도, 만약 0번 정점으로 돌아올 수 있는 노드가 없다면 ?? 그럼 다른 노드부터

   시작해야되는게 맞지 않을까?" 라고 생각할 수 있지만, 0번 정점으로 들어가는 노드가 없다면 아마 모든 도시를

   순회할 수 없을 것이다. 왜냐하면 0번 노드로 갈 수 없기 때문이다.

   즉 ! DFS를 모든 정점이 아닌, 하나의 정점에서만 호출하더라도 정답을 구할 수가 있다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 16
#define INF 987654321
using namespace std;
 
int N, Answer_Bit;
int MAP[MAX][MAX];
int Cost[MAX][1 << MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    Answer_Bit = (1 << N) - 1;
}
 
int DFS(int Cur_Node, int Cur_Bit)
{
    if (Cur_Bit == Answer_Bit)
    {
        if (MAP[Cur_Node][0] == 0) return INF;
        else return MAP[Cur_Node][0];
    }
 
    if (Cost[Cur_Node][Cur_Bit] != -1) return Cost[Cur_Node][Cur_Bit];
    Cost[Cur_Node][Cur_Bit] = INF;
    
    for (int i = 0; i < N; i++)
    {
        if (MAP[Cur_Node][i] == 0) continue;
        if ((Cur_Bit & (1 << i)) == (1 << i)) continue;
        
        Cost[Cur_Node][Cur_Bit] = Min(Cost[Cur_Node][Cur_Bit], MAP[Cur_Node][i] + DFS(i, Cur_Bit | 1 << i));
    }
    return Cost[Cur_Node][Cur_Bit];
}
 
void Solution()
{
    memset(Cost, -1, sizeof(Cost));
    cout << DFS(0, 1) << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}