[C++] 백준 - 10971 : 외판원 순회 2

문제 링크

10971번: 외판원 순회 2

 

풀이 ) DFS

  TSP 문제이다.

  도시의 수가 10개 이하이므로 DFS로 풀 수 있다.

  방문 여부를 나타내는 visited 배열을 만들어서 각 도시를 방문했을 때, 방문하지 않았을 때 순서대로 재귀를 하고 모든 도시를 방문하고 마지막 도시에서 시작 도시로 돌아올 수 있으면 그 값을 기존의 결괏값과 비교해 최솟값을 구한다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int n, city[10][10], visited[10], ans = 1e9;

void dfs(int curr, int len, int tot);

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

  dfs(0, 0, 0);
  if(ans == 1e9)
    printf("-1\n");
  else
    printf("%d\n", ans);
  return 0;
}

void dfs(int curr, int len, int tot)
{
  if(len == n-1){
    if(city[curr][0])
      ans = min(ans, tot+city[curr][0]);
  }
  else{
    for(int i = 1; i < n; ++i)
      if(city[curr][i] && !visited[i]){
        visited[i]++;
        dfs(i, len+1, tot+city[curr][i]);
        visited[i]--;
      }
    }
}