[백준] 2098 외판원 순회

April 27, 2021 ( last updated : April 27, 2021 )
비트마스크 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 2098번 외판원 순회

[백준] 2098번 외판원 순회

백준 2098번

알고리즘 유형

문제 이해

외판원이 순회할 때의 최소 순회 비용을 나타내라

풀이방법

비트마스크를 응용하여 손쉽게 풀 수 있다.

#include <algorithm>
#include <iostream>

using namespace std;
#define INF 987654321
int N, W[20][20], DP[20][1 << 20];

int dfs(int node, int visit) {
  if (visit == ((1 << N) - 1)) {
    return W[node][0];
  }
  if (DP[node][visit] != INF) {
    return DP[node][visit];
  }
  for (int i = 0; i < N; i++) {
    if ((visit & (1 << i)) == 0 && (W[node][i] != 0)) {
      DP[node][visit] =
          min(DP[node][visit], dfs(i, (visit | (1 << i))) + W[node][i]);
    }
  }

  return DP[node][visit];
}

int main() {
  cin >> N;
  for (int i = 0; i < 20; i++) {
    for (int j = 0; j < 20; j++) {
      W[i][j] = INF;
    }
    for (int j = 0; j < (1 << 20); j++) {
      DP[i][j] = INF;
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      int tmp;
      cin >> tmp;
      if (tmp != 0) {
        W[i][j] = tmp;
      }
    }
  }

  cout << dfs(0, 1);
  return 0;
}

Originally published April 27, 2021
Latest update April 27, 2021

Related posts :

{# #}