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

문제 링크 - https://www.acmicpc.net/problem/10971

🌱 문제

🌱 풀이

• 이 문제도 가능한 모든 수열을 순회하는 순서라고 두고 전부 확인해주면서 최솟값을 구했다.
• next_permutation 함수를 이용해 모든 수열을 돌면서, 각 수열의 순서대로 순회를 할때, 순회가 가능한지 체크하고 비용을 리턴하여 최솟값을 비교하였다.
• 경로가 없는 경우 0을 리턴받도록 했다.
• answer은 각 행렬의 성분은 최대 백만이고, N이 <=10이니까 최대 천만인데, 그냥 편하게 21억으로 놨다.

😱 헤맸던 점

• 이 문제 꽤나 오래걸렸는데 그 이유를 써보고 다음에 조심해야겠다.

1. 수열은 자연수라서 1부터시작이고 배열은 내가 index=0 부터 시작되게 설정했는데, 이걸 생각 못해서 계속 arr[v[i]]처럼 배열인덱스에 벡터값 자체를 넣고 생각했다. arr[v[i]-1] 이 맞는 비교이다.
2. 경로 비용을 더하고 마지막에 마지막 지점-> 처음 지정에 가는 경우에서 경로가 없을 수 있다는 생각을 못했다.
   -> 0인지 체크하고 0이면 0을 리턴받도록 고쳤다.
3. main함수에서 result=func(arr,v,n) 값이 0이어도 그냥 answer 비교로 넘어갔는데, (순간 최댓값 구하는걸로 착각함) 이 경우는 최솟값 구하는데에 무조건 영향 미치므로, 0인경우 continue를 해줬어야 했다.

🌱 코드

//10971번: 외판원 순회2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int arr[11][11];
int answer=2100000000;

int func(int arr[][11], vector<int> v, int n){
    int result=0;
 
   
    for(int i=0; i<n-1; i++){
         if(arr[v[i]-1][v[i+1]-1]==0){ //길이 없는 경우
            return 0;
         }
        
        //i에서 i+1로 갈수있는 경우에만 진행
            result+=arr[v[i]-1][v[i+1]-1];
        
    }
    //수열은 1,2,3,4 자연수고 인덱스는 0부터 시작하므로 1 빼줘야함.
    //마지막에, 처음 지점으로 돌아오는 비용 더해야함
    // n-1번째랑 0번째 길이 없는경우도 체크 해야함!
    
    if(arr[v[n-1]-1][v[0]-1]==0){
    return 0;
    }
    else{
    result+=arr[v[n-1]-1][v[0]-1];
    }
   
    return result;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    vector<int> v(n);
    for(int i=0; i<n; i++){
        v[i]=i+1;
    }


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


    do{
        int result=func(arr,v,n);
        // result=0 인경우는 경로가 없는 경우인데, continue를 안하고 0을 더하면 최솟값 구하는데에 영향을 미치게 됨
        if(result==0)
        continue;
        //  cout<<result<<"\n";
        if(answer>result)
        answer=result;

    }while(next_permutation(v.begin(),v.end()));

    cout<<answer<<"\n";
    

}