[백준 10971] 외판원 순회2

www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

브루트 포스 문제의 일종이다.

np problem중 하나로 인터넷에 검색해보면

dp + bit mask로 많은 풀이가 있다.

 

dp와 bit를 사용해서 풀기 전에 일반적인 dfs접근을 해보려고 한다.

 

문제에 대한 분석

1. 외판원 순회 문제

모든 도시들을 한번만 방문하여 처음 출발한 도시로 돌아올 때 최소 비용을 구하는 문제이다.

 

2. 출발 도시는 상관없다.

왜냐 어차피 사이클이 발생해서 처음으로 돌아오기 때문이다. 사이클은 중요하지 않다.

 

3. 도시가 이어져 있는지 확인

도시 사이가 이어져 있는지는 비용으로 계산한다. 비용이 0이라면 갈 수 없는 도시이다.

 

첫 번쨰 접근: dfs

#include <stdio.h>
#include <algorithm>

using namespace std;

int w[11][11];
bool visited[11];
int n;
int res = 1e9;

void dfs(int start, int cur, int sum, int cnt)
{
  // 만약 모든 도시를 돌고 종착지가 출발점이라면 최종 비용을 업데이트
  if (cnt == n && start == cur)
  {
    res = min(res, sum);
    return;
  }

  for (int i = 0; i < n; i++)
  {
    //다음 도시가 이미 방문한 도시거나 cur에서 갈 수 없는 곳이라면 패스
    if (visited[i] || w[cur][i] == 0)
      continue;

    visited[i] = true;
    sum += w[cur][i];

    if (sum <= res)
    {
      //비용을 더 낮출 수 있다면 다음 도시를 방문한다.
      dfs(start, i, sum, cnt + 1);
    }
    visited[i] = false;
    sum -= w[cur][i];
  }
}
int main(void)
{
  scanf("%d", &n);

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      scanf("%d", &w[i][j]);
    }
  }

  for (int i = 0; i < n; i++)
  {
    dfs(i, i, 0, 0);
  }

  printf("%d\n", res);
  return 0;
}

 

두 번째 접근: bit mask + dp

비트를 사용해서 visited 집합을 표현한다.

앞서 말했다 싶이 방문 순서와 출발점은 중요하지 않다. 따라서 방문한 도시를 집합으로 표현하게 되는데 이것을 비트로 표시할 수 있다.

 

dp[i][visited] 현재 위치는 i 도시이다. visited는 i를 포함한 여태 방문한 도시들이다.

만약 1,2,3 세 도시중 3 도시를 방문하고 현재 2라면

dp[2][110(2)] 요렇게 표시할 것이다.

 

dp 배열을 -1로 초기화하여 업데이트 여부를 확인한다.

 

#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

int w[11][11];
int dp[11][1 << 10];
int n;

int tsp(int cur, int visited)
{
  //전부 방문했다면
  if (visited == (1 << n) - 1)
  {
    //0으로 돌아간다.
    //현재 도시가 0과 이어지지 않았다면 무한대, 이어졌다면 비용을 리턴
    if (w[cur][0] == 0)
      return 1e9;
    else
      return w[cur][0];
  }

  int &ret = dp[cur][visited];

  // dp가 업데이트되었다면
  if (ret != -1)
    return ret;
  ret = 1e9;

  for (int i = 0; i < n; i++)
  {
    if (visited & (1 << i) || w[cur][i] == 0)
      continue;

    ret = min(ret, tsp(i, visited | (1 << i)) + w[cur][i]);
  }
  return ret;
}
int main(void)
{
  scanf("%d", &n);

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

  //출발지점이 상관없으므로 0에서 출발
  printf("%d\n", tsp(0, 1));
  return 0;
}