[algorithm] 백준 - 외판원 순회 2

이 문제는 brute force문제이다.

 

한 도시를 출발하여 n개의 도시를 다 거치고 원래 도시로 돌아오는 방법 중 최소 비용을 출력하는 문제이다.

 

시작점과 동일한 도시이고 n개의 도시를 순회했을 경우 최소비용을 구하도록 했다.

 

if(start == y && target == n){
        if(sum < minSum){
            minSum = sum;
        }
        return;
    }

 

그리고 y에서 시작했을 때 도시를 순회하기 위한 비용이 최소 비용을 넘지 않을 경우 계속해서 순회를 하도록 했다.

 

for(int i = 0; i < n; i++){
        if(visited[y] == 1 || path[y][i] == 0) continue;
        if(sum < minSum){
            visited[y] = 1;
            dfs(start, target + 1, i, sum + path[y][i]);
            visited[y] = 0;
        }
    }

 

모든 도시를 시작점으로 해서 순회하는 비용 중 최소 비용을 구했다.

 

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

 

따라서 전체적인 코드는 이렇다.

 

//외판원 순회 2
#include <iostream>
using namespace std;
int visited[11];
int path[11][11];
int n, minSum = 987654321;
void dfs(int start, int target, int y, int sum){
    if(start == y && target == n){
        if(sum < minSum){
            minSum = sum;
        }
        return;
    }
    for(int i = 0; i < n; i++){
        if(visited[y] == 1 || path[y][i] == 0) continue;
        if(sum < minSum){
            visited[y] = 1;
            dfs(start, target + 1, i, sum + path[y][i]);
            visited[y] = 0;
        }
    }
}
int main(void){
    cin >> n;
    fill_n(visited,11,0);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> path[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        dfs(i, 0, i, 0);
    }
    cout << minSum;
}