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

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 987654321;
const int MAX_N = 16;
int n, dist[MAX_N][MAX_N], dp[MAX_N][1 << MAX_N]; // 불리언 배열처럼 사용해서 방문처리 효과

int tsp(int here, int visited) {
  // 모두 방문한 경우
  if(visited == (1 << n) - 1) {
    return dist[here][0] == 0 ? INF : dist[here][0];
  }
  int &k = dp[here][visited];
  // 이미 구해져 있는 경우
  if(k != -1) return k;
  k = INF;
  // i번째 bit가 비어있을 때, i번째 비트를 비우고 탐색(재귀)
  for(int i = 0; i < n; i++) {
    if(visited & (1 << i)) continue; // 방문한 곳이 1개라도 겹친다면 continue
    if(dist[here][i] == 0) continue; // here에서 i로 가는 길이 없다면 continue
    k = min(k, tsp(i, visited | (1 << i)) + dist[here][i]);
  }
  return k;
}

int main() {
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      scanf("%d", &dist[i][j]);
    }
  }
  memset(dp, -1, sizeof(dp));
  printf("%d\n", tsp(0,1));
}

외판원 순회 문제는 dp로 해결할 수 있는 엄청 유명한 문제 중 하나라고 한다. 처음에는 팩토리얼을 돌려야 하나 싶었는데 그러면 엄청난 시간이 걸릴 거 같아서 다른 방법을 생각했다. 다행히 엄청 똑똑한 누군가가 O(2^n*n^2)로 해결하는 방법을 만들어 두었고, 이 아이디어를 가져왔다. 순회할 그래프를 만들어주고, 값을 저장할 dp 배열을 만들어준다. 이때 dp 배열의 첫번째 요소는 현재 위치가 어디인지를 저장하고, 두번째 요소에는 방문현황을 저장해준다.

비트연산자를 사용한 이유는, 최대 16차원의 배열이 필요한데 이를 다 생성하기보다는 비트값을 이용해 계산하는 것이 효율적이기 때문이다. 그래프를 순회하면서, 최소값을 찾아주면 된다.