image

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

Traveling Salesman Problem (TSP) (외판원 순회 2)

풀이 과정

  • 이 문제는 외판원 순회 문제로, 모든 도시를 거쳐 다시 원래의 도시로 돌아오는 순회 여행을 돌면서 발생하는 비용의 최소를 구해야 한다.
  • 간단히 이 문제를 생각해보면, 그냥 다 돌면서 비교해보고 최솟값을 바꿔가면서 최종적으로 저장되어있는 비용의 최솟값을 출력하면 된다.
  • 하지만 이 방법은 모든 작업 일일이 다 해야하므로, 비효율적이고 오랜 시간이 소요되는 작업이다. 그래서 효율적인 방법을 찾아야한다.

  • 그래서 생각해보니 아래와 같은 규칙이 적용이 되었다. ​

  • 아래와 같은 루트들의 비용이 똑같다는 것은 간단히 알 수 있다.
    • 1 2 3 1
    • 2 3 1 2
    • 3 1 2 3
  • 즉, 맨 앞 하나가 어떤 값이던 간에 변화가 없다. 그래서 하나를 제외하고 반복. (N+1)! 와 N!의 차이를 만든다. 가장 큰 값 하나를 곱하는 것을 제외하고 작업한다는 것은 큰 차이이다.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 백준 10971번: 외판원 순회 2 (Traveling Slesman problem: TSP)
// 백트래킹, 브루트포스 알고리즘

int W[11][11];
int ret;
vector<int> permu;
int N;

bool calculation() {
    ret = 0;
    for (int i = 0; i < N; i++) {
        if ( W[permu[i]][permu[(i + 1) % N]] == 0 )
           return false;
        ret += W[permu[i]][permu[(i + 1) % N]];
        cout << "ret: " << ret <<"\n";
    }
    return true;
}

int main() {   
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> W[i][j];
        }
        //cout << "i: " << i << "\n";
        permu.push_back(i); // 1, 2, 3, 4
    }
    
    int answer = 2e9;
    do
    {
        answer = calculation() ? min(answer, ret) : answer;
        cout << "answer: " << answer << "\n";
    } while (next_permutation(permu.begin() + 1, permu.end())); //


    cout << answer << "\n";
 
    return 0;
}