백준 10971번 외판원순회2 (C++) 🚩

next_permutation은 {1,2,3,4} 가 주어지면 1,2,4,3 과 같이 다음에 넘어갈 수열이 있으면 실행

prev_permutation은 {1,2,4,3}이면 {1,2,3,4} 과 같은게 있으면 실행한다. 

#include<vector>
#include <iostream>
#include<algorithm>

using namespace std;

vector<vector<int>>arr;
    
int cal(vector<int>visited){
    
    visited.push_back(visited[0]);
    
    //중간에 길 끊기면 경로 아님 
    int cnt=0; 
    for(int i=0;i<visited.size()-1;i++){
        int start=visited[i]; 
        int dest=visited[i+1];
        
        if(arr[start][dest]==0)return 100000000;
        cnt+=arr[start][dest];
    }
    return cnt; 
}


int main()
{
    int n;
    cin>>n;
    
    vector<int>visited;

    arr.assign(n,vector<int>(n,0));
    visited.assign(n,0);
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>arr[i][j];
        }
        visited[i]=i; 
    }
    
    //1->2->3->4..n부터 시작 
    int ans=10000000;
    
    do{
        
        ans=min(ans,cal(visited));
        
    }while(next_permutation(visited.begin(),visited.end()));
    
    cout<<ans;
    
    return 0;
}