10971 외판원 순회 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	34091	12343	7317	34.099%

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

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

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

35

코드

import java.io.*;
import java.util.Arrays;

public class P_10971 {

    static int[][]  info;
    static int[]    perm;
    static int      min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
        int             n = Integer.parseInt(br.readLine());

        info = new int[n][n];
        for (int i = 0; i < n; i++)
            info[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        perm = new int[n];
        for (int i = 1; i<= n; i++) perm[i - 1] = i;

        do {
            int cost = itinerant_route();
            if (cost != -1)
                min= (min < cost) ? min: cost;
        } while(find_next_perm());

        System.out.print(min);
    }

    public static boolean find_next_perm() throws IOException {

        int idx = -1;

        for (int i = perm.length - 2; i>= 0; i--) {
            if (perm[i] < perm[i + 1]) {
                idx = i;
                break;
            }
        }

        if (idx == -1) return false;
        else {
            for (int j = perm.length - 1; j > idx; j--) {
                if (perm[j] > perm[idx]) {
                    int temp = perm[j];
                    perm[j] = perm[idx];
                    perm[idx] = temp;
                    break;
                }
            }
            Arrays.sort(perm, idx + 1, perm.length);
            return true;
        }

    }

    public static int itinerant_route() {

        int cost = 0;

        for (int i = 0; i < perm.length; i++) {
            int medium_cost = info[perm[i] - 1][perm[(i + 1) % perm.length] - 1];

            if (medium_cost == 0) return -1;
            else cost += medium_cost;
        }

        return cost;
    }
}

코드 설명

[P.10972 다음 순열]의 코드를 이용했다. 이 코드를 이용하더라도 N이 최대 10이기 때문에 연산 수가 1억을 넘지 않는다.

첫째 줄에 도시의 수 N이 주어지는데 N이 4라면 외판원은 도시를

1->2->3->4->1
1->2->4->3->1
.
.
.
4->3->2->1->4

이런 식으로 순회할 수 있다.
즉, 모든 도시 순열을 순회하면 외판원이 순회할 수 있는 도시의 모든 가지 수를 구할 수 있는 것이 된다.

그래서 주어진 N을 이용하여 도시의 인덱스를 매겼고 첫 시작은 [1][2][3][4][...][N]으로 하였다.
이제 다음 순열이 없을 때까지 find_next_perm이 구해준 순열을 이용하여 itinerant_route에서 cost를 구하면 된다.

만약 perm이 [1][2][3][4] 순이라면 전체를 순회하면서 1->2의 중간 순회 비용을 info[0][1]로 찾고, 2->3의 중간 순회 비용을 info[1][2]로 찾는다. 마지막 4->1을 찾기 위해서 i + 1을 perm.length(즉, N)으로 나눈 나머지 값으로 설정했다.

문제에서는 갈 수 없는 도시도 있다고 했는데 이 때 cost를 0으로 설정했다고 한다.
그렇기 때문에 예시에서 볼 수 있듯이 i에서 i로의 도시 이동은 불가능하고, 예시에서 보이지 않는 부분일 경우 i에서 j로의 도시 이동인데 cost가 0일 경우이다.

처음에는 후자의 경우의 조건을 추가하지 않아서 틀렸는데 medium_cost가 0이 되면 -1을 반환해서 min값을 갱신하지 못하도록 하였다.