백준 10971 외판원 순회 2

N이 최대 10일 때 10개의 도시 목록을 배열에 넣고 next_permutation을 통해서 풀면된다.

원소가 10개 이하이기 때문에 브루트 포스로 풀 수 있는 문제다.

한 번 갔던 도시로는 다시 갈 수 없기 때문에 순열로 풀 수 있는 문제다.

 

시작점은 중요하지 않다.

만약 4개의 도시가 있다면 1 -> 2 -> 3 -> 4 -> 1 이 루트와 2 -> 3 -> 4 -> 1 -> 2 이 루트에 필요한 비용은 같기 때문이다.

따라서 시작점을 정해놓고 알고리즘 풀이를 하기 때문에 시간 복잡도가 O(N * N!)보다 작다.(O( (N-1) * (N-1)!))

 

처음에 순서대로 도시 번호를 넣어준 다음 순열을 돌리면서 모든 경로의 수를 구한다.

자세한 설명은 주석으로..

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main(int argc, char** argv) {
    int n, min = -1;//무조건 양의 값이 나오므로, 초기 값을 음수로 설정하여, 첫 번째 계산시 min값이 음수면 첫 sum의 값을 초기화할 수 있도록 한다.
    int city[100][100];
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> city[i][j];
        }
    }
 
    vector<int> v(n);
    for (int i = 0; i < n; i++)v[i] = i;//도시 순서를 섞기 위해 도시번호를 순열로 vector에 넣는다.
 
    do {
        int sum = 0;
        int ok = true;//do-while문과 for문이 중첩되어 있으므로, 구분하기 위해 ok라는 bool 변수를 둔다.
        for (int i = 0; i < v.size() - 1; i++) {
            if (city[v[i]][v[i + 1]] != 0) {//배열의 index값으로 배열의 값이 올 수 있다. 이러한 방식을 잘 써먹을 것.
                sum += city[v[i]][v[i + 1]];
            }
            else {//경로가 없을 경우 false로 설정하고, for문을 빠져나간다.
                ok = false;
                break;
            }
        }
        if (city[v[v.size() - 1]][v[0]] != 0 && ok == true) {//0번 도시가 fix기 때문에 마지막 도시에서부터 0번으로 오는 경로를 더해준다.
            sum += city[v[v.size() - 1]][v[0]];
            if (min < 0 || min > sum)min = sum;//min값이 음수면 처음으로 초기화 될 것. 혹은 sum 값이 min보다 작으면 초기화 될 것.
        }
    } while (next_permutation(v.begin() + 1, v.end()));//1 -> 2 -> 3 -> 4 -> 1 이 루트와 2 -> 3 -> 4 -> 1 -> 2 이 루트에 필요한 비용은 같기 때문에 시작점을 0번 도시로 fix한다.
 
    printf("%d\n", min);
 
    return 0;
}