[백준] 19071. 외판원 순회2 - C++

문제 설명

1번부터 N번까지의 도시가 있을 때, 한 도시에서 출발하여 각 도시를 한 번만 방문하고 출발한 도시로 돌아오는 경로의 최소비용을 구하는 문제

 

• 알고리즘 분류 - 브루트포스, (백트래킹, DP?)
• 난이도 - 실버2

---

관련 개념

C++에서 순열 사용하기 - std::next_permutation

https://cplusplus.com/reference/algorithm/next_permutation/

https://cplusplus.com/reference/algorithm/next_permutation/

 

---

접근 방법

1. Brute Force

N이 10 이하기 때문에 브루트 포스가 가능하다. 순열을 이용한다.

모든 경로를 순열로 나타내고, 각 수열의 비용을 구해 최솟값을 찾는 것이다.

가령, N=4일 때,

1 2 3 4

1 3 2 4

1 4 2 3

2 1 3 4

...

와 같이 모든 경로를 순열로 나타내고, 각 수열을 순회하며 W[현재 도시 번호-1][다음 도시 번호-1]를 비용에 누적한다.

이후 마지막 도시에서 출발지를 가는 데에 드는 비용이 0이 아니라면, 해당 비용을 누적한다.

 

다만, 위 방법은 파이썬으로 실행할 경우 시간 초과가 날 수 있다.

 

(백트래킹, DP로도 풀 수 있을 것 같은데 풀게 되면 추가할 예정)

---

답안 코드 - Brute Force

메모리: 2020 KB , 시간: 720 ms, 코드 길이: 1200 B

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

using namespace std;

int solution(int n){
    int W[n][n];
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> W[i][j];
        }
    }
    
    int min = 1e9; // 각 비용이 1,000,000 이하의 수이므로 min을 넉넉하게 잡아주어야 함
    
    vector<int> idxs(n); // 도시 번호(순열 함수를 실행하기 위해 벡터가 필요하기 때문에 만듦)
    
    for(int i=0; i<n; i++){
        idxs[i] = i;
    }
    
    do{
        vector<int> seq; // 순열의 각 수열
        
        for(int i=0; i<n; i++){
            seq.push_back(idxs[i]);
        }
        
        int start = seq[0];
        int end = seq[seq.size()-1];
        
        int cost = 0;
        
        for(int i=0; i<seq.size()-1; i++){
            if (W[seq[i]][seq[i+1]] == 0){
                cost = -1;
                break;
            }
            cost += W[seq[i]][seq[i+1]];
        }
        
        if (cost == -1) continue;
        
        if (W[end][start] == 0){
            cost = -1;
            continue;
        }
        
        cost += W[end][start];
        
        if (cost < min){
            min = cost;
        }
        
    }while(next_permutation(idxs.begin(), idxs.end()));
    
    return min;
}

int main()
{
    int N;
    cin >> N;

    cout << solution(N);

    return 0;
}