[Baekjoon]백준 10971번 외판원순회2

10971번 외판원 순회2 문제 풀이

문제

• 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 어느 한 도시에서 출발하여 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단 한 번 갔던 도시로는 갈 수 없다. 각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어지며 도시 i에서 도시 j로 가기위한 비용을 나타낸다. 갈 수 없는 도시 및 자기자신은 항상 0이된다. 가장 적은 비용을 들이는 여행 계획을 세워라.

입력

• 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.
  항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

• 첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제

입력
4
0 10 15 20
5  0  9 10
6 13  0 12
8  8  9  0

출력
35

해결방법

• 모든 도시를 한 번씩 순회하는 방법으로는 도시를 순열형태로 만들어서 다음 순열을 탐색해가며 각 순열마다 이동경로의 값을 구하여 최소 값을 저장시키는 방법을 사용한다.

변수&함수	내용
d[]	순열을 생성한다.
a[][]	이동 경로의 값을 저장한다.
sum	이동 경로의 합을 저장한다.
ans	최소 값을 저장한다.
check	해당 경로의 길이 존재하는지 확인한다.
next_permutation_self	다음 수열을 구하는 함수를 구현했다.

• 우선 STL의 next_permutation을 사용하지 않고 다음 수열을 구하는 함수를 직접 구현하였다. do-while문을 사용하여 수열을 처음부터 끝까지 탐색할 수 있도록 한다.

• d[]는 첫 인덱스부터 마지막 인덱스까지 이동경로가 차례대로 저장된다. if문에서 a[d[i]][d[i + 1]] == 0인 경우에만 check를 false로 바꿔주고 아닐시 sum에 이동 비용을 더해준다.

  for (int i = 0; i < n - 1; i++) {
    if (a[d[i]][d[i + 1]] == 0) check = false;
    else {
        sum += a[d[i]][d[i + 1]];
    }
  }

• 처음부터 끝까지 이동하였으면 다시 자기 자신에게 돌아와야한다. 이 때 주의할점은 check가 false면 이 경로는 끊어진 경로라고 볼 수있으니 다음 수열로 넘어가도록 해야한다.

  if (check && a[d[n - 1]][d[0]] != 0) {
    sum += a[d[n - 1]][d[0]];
    if (ans > sum) ans = sum;
  }

코드

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int a[11][11];
int d[11];
int n;

bool next_permutation_self(int *a) {
    int i1 = 0, j1;
    for (int i = 1; i < n; i++) {
        if (a[i - 1] < a[i]) {
            i1 = i;
        }
    }
    if (i1 == 0) return false;

    for (int j = i1; j < n; j++) {
        if (a[j] > a[i1 - 1]) {
            j1 = j;
        }
    }
    swap(a[j1], a[i1 - 1]);
    sort(a + i1, a + n);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    int ans = 987654321;
    for (int i = 0; i < n; i++) {
        d[i] = i;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
                cin >> a[i][j];
        }
    }
    do {
        int sum = 0;
        bool check = true;
        for (int i = 0; i < n - 1; i++) {
            if (a[d[i]][d[i + 1]] == 0) check = false;
            else {
                sum += a[d[i]][d[i + 1]];
            }
        }
        if (check && a[d[n - 1]][d[0]] != 0) {
            sum += a[d[n - 1]][d[0]];
            if (ans > sum) ans = sum;
        }
    } while (next_permutation_self(d));

    cout << ans << '\n';
    return 0;
}