[백준] 10971 외판원 순회(C++)

 

문제 URL:

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

다음은 도시의 수와 비용 행렬이 주어졌을 때 외판원의 순회에 필요한 최소 비용을 출력하는 문제로

깊이 우선 탐색(dfs)을 통한 전체 탐색을 진행하는 문제이다. 

 

dfs를 통해서 현재 위치에서 갈 수 있는 모든 지점을 탐색해 준다. 

이때 최소 비용을 찾아야 하기 때문에 비용 행렬을 더한 값이 현재 최소 비용(total_cost)보다 커진다면 더 이상 순회를 진행하지 않는다. 

---

#include <iostream>
#include <string.h>
using namespace std;

int map[11][11];
int visited[11];
int n;
int total_cost = 987654321;

void dfs(int start, int now, int sum, int cnt) {
  if (cnt == n && start == now) {  // 시작점으로 되돌아 온 경우
    if (total_cost > sum)
      total_cost = sum;
    return;
  }

  for (int i = 0; i < n; i++) {
    if(map[now][i] == 0)  // 연결되지 않은 경우, 자기 자신인 경우
      continue;
    
    if(!visited[now]) {
      visited[now] = true;
      sum += map[now][i];
      if(sum <= total_cost) {  // sum이 total_cost보다 작을 때만 dfs를 진행시켜 시간을 최소화 시켜줌
        dfs(start, i, sum, cnt+1);
      }
      // 방문 기록과 합 초기화(백트레킹)
      visited[now] = false;
      sum -= map[now][i];
    }
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      cin >> map[i][j];
    }

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

  cout << total_cost;
  return 0;
}

참고: https://blockdmask.tistory.com/229