[Backjoon_10971] 외판원 순회 2

문제링크

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

10971번: 외판원 순회 2

문제설명

문제

외판원 순회 문제는 영어로 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로 가기 위한 비용을 나타낸다.

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

출력

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

제한사항

제한시간	메모리 제한
2초	256MB

 

문제풀이

브루트포스로 순열을 활용하여 해결할 수 있다.

입력으로 오는 N이 최대 10이다. 따라서 N개의 수의 순열을 만들어도 경우의 수는 10!밖에 되지 않는다.

연산을 해봤자 N정도로 마무리 될 수 있으니 시간복잡도는 O(N*N!)으로 마무리될 수 있다고 생각하고 브루트포스로 접근하였다.

 

    public static boolean nextPermutation(int[] list) {
        int n = list.length;
        int prevIndex;
        int nextIndex = n-1;
        for(int i = n-2; i >= 0; i--){
            prevIndex = nextIndex;
            nextIndex = i;
            if(list[nextIndex] < list[prevIndex])
                break;
        }
        int changeIndex = -1;
        for(int i = nextIndex; i < n; i++){
            if(list[nextIndex] < list[i])
                changeIndex = i;
        }
        if(changeIndex == -1)
            return false;

        swap(list,changeIndex,nextIndex);
        while(nextIndex < n){
            nextIndex++;
            n--;
            swap(list,nextIndex,n);
        }
        return true;
    }

다음 순열을 구하는 코드를 구현한 것이다. 이 때 나는 Index를 0~n-1까지의 수로 보고 해당 값에 대한 순열로 연산을 처리하였다. 

 

다음순서를 구하는 방법은 아래와 같다.

1. 맨 우측에서부터 넣어줄 위치 찾기

2. 해당 위치와 바꾸어줄 값 뒤에서 찾기

3. 서로 교환해서 다시 오름차순으로 바꾸어 두기

 

        int prevIndex;
        int nextIndex = n-1;
        for(int i = n-2; i >= 0; i--){
            prevIndex = nextIndex;
            nextIndex = i;
            if(list[nextIndex] < list[prevIndex])
                break;
        }

1번을 해결하기 위해서 우리는 위와 같은 코드를 실행한다.

코드를 보면 뒤에서부터 비교해 prev값이 더 커지는 경우에서 멈추는 것을 볼 수 있다. 해당 nextIndex의 값을 바꾸어주어야 한다.

이를 이해하기 위해 예를 들어보자.

1 4 5 3 2의 다음 순열을 구하면 1 5 2 3 4이다.

우리는 1 4 5 3 2 중 빨간글씨 부분을 주목해서 봐야한다. 보면 next가 point하는 위치가 항상 커짐을 알 수 있다. 

하지만 1 4 5 3 2 4와5의 지점에서 next와 prev의 관계가 역전된다.

그렇다면 우리가 사전순으로 고려하였을 때 가장 최소로 변경하는 방법은 바로 4의 값 위치에 4 이후에 오는 값들중에 최소값 그리고 4보다 큰 값을 넣어주면 되는 것 이다.

 

        int changeIndex = -1;
        for(int i = nextIndex; i < n; i++){
            if(list[nextIndex] < list[i])
                changeIndex = i;
        }
        if(changeIndex == -1)
            return false;

        swap(list,changeIndex,nextIndex);

위 예시에서 이해를 하였다면 다음 2번을 위해 동작하는 위 코드도 이해가 될 것이다.

changeIndex가 바로 우리가 찾아준 바꿔줄 위치 뒤 부분 중 조건을 만족하는 값일 것이다.

그런데 예외상황이 하나있다. 바로 순열이 끝순열인 경우이다.

이 경우 조건을 만족하는 값을 찾지 못한다.(next보다 커야하지만 가장 큰 값이므로)

따라서, 마지막이라는 의미로 false를 return해주었다.

 

        while(nextIndex < n){
            nextIndex++;
            n--;
            swap(list,nextIndex,n);
        }

마지막으로는 3번 내용을 구현한 것이다.

현재 2번까지 완료한 순열의 상태는 1 5 4 3 2이다. 이때 5 뒤에 오는 데이터는 다시 내림차순으로 바꾸어주어야한다.

정렬이 되어있으므로 다시 정렬하는 알고리즘을 사용하는 것보다는 교차로 swap하여 내림차순으로 바꾸어준다.

 

이렇게 3가지 방법으로 다음 순열을 구해주었다.

 

		do{
            int sum = 0;
            int i = 0;
            for(; i < n; i++){
                if(w[list[i%n]][list[(i+1)%n]] == 0)
                    break;
                sum += w[list[i%n]][list[(i+1)%n]];
            }
            if(i == n){
                min = min > sum ? sum : min;
            }
        }while(nextPermutation(list));

이제 위에서 구현한 다음 순열로 list를 옮기는 메소드를 활용해 구현해보도록 하겠다. 

%n 연산자로 나누어주는 이유는 결과에  마지막 지점에서 다시 처음 지점으로 돌아가는 값이 포함되어야 하기 때문이다.

nextPermutation으로 계속 list를 옮겨가며 실행을 해준다.

 

이때, list의 초기 상태는 오름차순으로 정렬이 되어 있는 순열이어야 할 것이다.(초기 순열)

 

구현코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] w = new int[n][n];
        int[] list = new int[n];

        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                w[i][j] = sc.nextInt();
            }
        }

        for(int i = 0; i <n; i++){
            list[i] = i;
        }

        int min = Integer.MAX_VALUE;
        do{
            int sum = 0;
            int i = 0;
            for(; i < n; i++){
                if(w[list[i%n]][list[(i+1)%n]] == 0)
                    break;
                sum += w[list[i%n]][list[(i+1)%n]];
            }
            if(i == n){
                min = min > sum ? sum : min;
            }
        }while(nextPermutation(list));
        System.out.println(min);
    }

    public static boolean nextPermutation(int[] list) {
        int n = list.length;
        int prevIndex;
        int nextIndex = n-1;
        for(int i = n-2; i >= 0; i--){
            prevIndex = nextIndex;
            nextIndex = i;
            if(list[nextIndex] < list[prevIndex])
                break;
        }
        int changeIndex = -1;
        for(int i = nextIndex; i < n; i++){
            if(list[nextIndex] < list[i])
                changeIndex = i;
        }
        if(changeIndex == -1)
            return false;

        swap(list,changeIndex,nextIndex);
        while(nextIndex < n){
            nextIndex++;
            n--;
            swap(list,nextIndex,n);
        }
        return true;
    }

    public static void swap(int[] list, int a, int b){
        int temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }
}

 

시간복잡도

이 문제의 시간복잡도는 순열의 수 n! * 가중치 덧셈 n을 해서 O(n*n!)이다.

더 빠르게 문제를 해결하기 위해서는 Permutaion을 구해줄 때 가중치가 0이 되는(연결이 x) 부분이 들어갈 경우 바로 백트래킹으로 넘기는 방법이 있을 수 있다.