[백준] 2098번 외판원 순회

2098번 외판원 순회

---

1. 이해하기

• 비트마스크와 DP를 이용하는 문제이다.
• 비트마스크를 이용하여 방문한 지점을 체크하고 DP를 이용하여 특정 지점까지의 최소거리를 갱신한다.

---

2. 구현하기

• TSP(current,visited)일때 방문한 지점은 visited & (1<<next) 로 확인할 수 있다.

  • 기저사례: visited가 (1<<N)-1과 같으면 모든 지점을 방문한 상태이다. 이때 처음지점으로 돌아갈 수 있는지 확인해서 돌아갈 수 있으면 그때의 cost를, 없으면 INF값을 줘야한다.
  • 다음으로 방문할 지점을 체크해서 갈 수 있으면 간다.
  • 시작지점은 어떤 점으로 설정해도 값은 같기 때문에 0에서 시작한다고 생각한다.

  int TSP(int current, int visited) {
      if(visited == (1<<N)-1)
          return (cost[current][0])?cost[current][0]:INF;
      int& ret = cache[current][visited];
      if(ret != -1) return ret;
      ret = INF;
      for(int i = 0; i < N; i++) {
          if(visited & (1<<i)) continue;
          if(cost[current][i] == 0) continue;
          ret = min(ret,TSP(i,visited | (1<<i))+cost[current][i]);
      }
      return ret;
  }

---

3. 전체코드

#include <iostream>
#include <cstring>
using namespace std;
int N,cost[16][16],cache[16][(1<<16)];
const int INF = 987654321;

int TSP(int current, int visited) {
    if(visited == (1<<N)-1)
        return (cost[current][0])?cost[current][0]:INF;
    int& ret = cache[current][visited];
    if(ret != -1) return ret;
    ret = INF;
    for(int i = 0; i < N; i++) {
        if(visited & (1<<i)) continue;
        if(cost[current][i] == 0) continue;
        ret = min(ret,TSP(i,visited | (1<<i))+cost[current][i]);
    }
    return ret;
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> cost[i][j];
    memset(cache,-1,sizeof(cache));
    cout << TSP(0,1) << '\n';
    return 0;
}