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

비트마스크, 다이나믹프로그래밍 문제입니다.

최소의 비용으로 모든 도시를 들려서 처음 출발한 도시로 도착하는 문제입니다.

다음의 비용은 동일합니다.

A -> B -> C -> D -> A
B -> C -> D -> A -> B
C -> D -> A -> B -> C
D -> A -> B -> C -> D

각각의 도시를 들렀을 때 최소값을 저장해가면서(DP) 최소비용을 찾습니다.
이 때 해당 도시를 들렸는지 확인하는 과정에서 비트마스크를 사용합니다. 

cost[x][y]에서 x는 현재위치, y는 방문한 도시들을 담고있습니다.
cost[3][15]는 현재 위치는 3이고 1, 2, 3, 4의 도시를 방문한 상태입니다.
(15 = 1 + 2 + 4 + 8)

1. 모든 도시를 방문했는지 확인
1-true. 시작점으로 돌아갈 수 있는지 확인
1-true-true. 시작점으로 돌아가는 비용 반환
1-true-false. INF값 반환
1-false. 2로 이동

2. 현재 위치 이미 계산했는지 확인
2-true. 계산된 값 반환
2-false. 3으로 이동

3. 방문하지 않은 도시들 체크 (1으로 이동)
3-1. 방문한 도시는 패스
3-2. 해당 도시로의 비용이 0인경우 패스
3-3. (방문하지 않은 도시 반환값 + 현재위치에서 방문하지 않은 도시의 비용) 가장 작은 비용으로 대입
3-4. 4로 이동

4. 계산된 비용 반환

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX_BIT 65536
#define INF 987654321
using namespace std;

int n;
int cost[16][MAX_BIT];
vector<vector<int>> v;

void input()
{
  int num;
  vector<int> temp;

  cin >> n;

  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < n; ++j)
    {
      cin >> num;
      temp.push_back(num);
    }
    v.push_back(temp);
    temp.clear();
  }
}

int solve(int location, int visitState)
{
  if (visitState == (1 << n) - 1)
  {
    return v[location][0] ? v[location][0] : INF;
  }

  int &ret = cost[location][visitState];
  if (ret != -1)
  {
    return ret;
  }

  ret = INF;
  for (int i = 0; i < n; ++i)
  {
    if (visitState & (1 << i))
    {
      continue;
    }
    if (v[location][i] == 0)
    {
      continue;
    }

    ret = min(ret, solve(i, visitState | (1 << i)) + v[location][i]);
  }

  return ret;
}

void solution()
{
  memset(cost, -1, sizeof(cost));

  cout << solve(0, 1) << endl;
}

int main(int argc, char *argv[])
{
  input();
  solution();

  return 0;
}