[백준,c++] 10971번 - 외판원 순회2

문제

10971번: 외판원 순회 2

 

코드

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

int N, min_cost = 1e9;
int graph[11][11];
int visited[11];


void dfs(int start, int node, int cost, int depth){\
    if(depth == N && node == start){
        min_cost = min(min_cost, cost + graph[node][start]);
        return;
    }
    for(int i=0; i<N; i++){
        if(!visited[i] && graph[node][i] && cost<min_cost){
            visited[i] = 1;
            dfs(start, i, cost+graph[node][i], depth + 1);
            visited[i] = 0;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            cin>>graph[i][k];
        }
    }
    
    for(int i=0; i<N; i++){
        dfs(i, i, 0, 0);
        memset(visited, 0 ,sizeof(visited));
    }
    cout<<min_cost;
}

 

풀이

외판원 순회란 Traveling Salesman problem (TSP) 라고도 불리며, 그래프에서 출발 정점에서 다른 모든 정점들을 방문하고 원래의 출발 정점으로 되돌아오는 순환 경로들 중에서 가중치의 합이 최소가 되는 순환 경로를 찾는 문제입니다.

즉, 경로가 5개의 노드가 있을 때 1 -> 2 -> 3 -> 4 -> 5 -> 1 이런 식으로 돌아올 때 가중치의 합이 가장 최소가 되는 경로를 찾는 문제입니다.

위 문제에서는 최소 비용을 출력하라고 했기 때문에 백트랙킹을 돌려서 최소 비용만 계속 갱신해가며 최종적으로 출력하면 됩니다.