[백준/c++] 10971번: 외판원 순회 2

 

 

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

10971번: 외판원 순회 2

 

 

이 문제는 백트래킹으로 1~N개의 도시를 모두 돌면 된다. 그러니까 N개를 골라서 걸리는 비용을 구하고 최소 비용을 구하면 된다.

시작 도시로 다시 돌아가야 되니까 마지막 도시에서 첫 도시로 돌아가는 비용도 더해줘야 한다. vector에 도시를 넣어서 순서가 정해지면

이 도시들을 i, i+1 사이의 비용을 sum에 더하는데 마지막 도시는 i+1 도시가 없으니까 0으로 돌려준다.

 

여기서 주의할 것은 바로바로 바로바로 w[i][j] = 0의 경우다. (만약 40%에서 틀렸다면 이 문제였을 겁니다.. 제가 그랬거덩요ㅋ)

이 경우는 그냥 이동을 못한다. 그러므로 이 부분은 빼줘야 한다.

그래서 나는 만약 w[i][j] == 0라면 그냥 바로 빠져나오도록 했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, arr[11][11];
int ans = 10000000;
bool visit[11];
vector<int> v;

void BT(int cnt){
    if(cnt == n){
        int sum = 0;
        for(int i=0; i<v.size(); i++){
            if(i == n-1){
                if(arr[v[i]][v[0]] == 0) return;
                sum += arr[v[i]][v[0]];
            }else{
                if(arr[v[i]][v[i+1]] == 0) return;
                sum += arr[v[i]][v[i+1]];
            }
        }
        ans = min(ans, sum);
        return;
    }
    
    for(int i=0; i<n; i++){
        if(!visit[i]){
            visit[i] = true;
            v.push_back(i);
            BT(cnt+1);
            visit[i] = false;
            v.pop_back();
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) cin >> arr[i][j];
    BT(0);
    cout << ans << '\n';
    return 0;
}