[알고리즘 PS] 백준 10971번 외판원 순회 2 자바 문제풀이

문제

해당 포스팅은 백준의 10971번 외판원 순회 2 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

10971번: 외판원 순회 2

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이번 문제는 CS 분야에서 유명한 문제라고 한다.

이 문제의 핵심은 다음과 같다.

n by n 행렬에서 (n, m)은 혹은 arr[n][m]은 n에서 m으로 가는 비용 이다.

우리는 이 비용을 최소화해야 한다.

 

아래와 같이 4 x 4 행렬이 있다면

0 1 2 1
3 0 3 2
1 2 0 1
2 1 2 0

0 -> 1   1 -> 2   2 -> 3   3 -> 0 // 이렇게 가던
1 -> 3   3 -> 2   2 -> 0   0 -> 1 // 혹은 이렇게 가던 상관 없음

어떻게 가던 모든 도시만 다 방문하면 된다.

 

그럼 모든 도시를 다 방문하려면 순열을 이용하면 될 것 같다.

 

하지만 순열 알고리즘은 시간 복잡도가 N * N! 가 된다.

N * N! 는 전혀 작지 않은 시간 복잡도이니 최악의 경우까지 계산해봐야 하는데, 10 * 10! = 36,288,000 으로 2초 내에 해결할 수 있는 충분한 양이 된다.

 

그럼 우리는 도시를 방문하는 순서를 순열로써 나타내고 그 가중치들만 계산해주면 순회에 필요한 최소 비용을 찾을 수있을 것 같다.

해결법

모든 순열을 구하기 위해서 우리는 Next Permutation을 이용할 것이다.

private static boolean nextPermutation(int[] arr) {
    int i = arr.length-1;
    while(i > 0 && arr[i-1] >= arr[i]) i--;
    if(i <= 0) return false;

    int j = arr.length-1;

    while(arr[j] <= arr[i-1]) j--;

    swap(arr, i-1, j);
    j = arr.length - 1;
    while(i < j) {
        swap(arr, i, j);
        i++;
        j--;
    }
    return true;
}

private static void swap(int[] arr, int index1, int index2) {
    int temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

오답 후보

이 문제에서 가장 주의해야 하는 것은 바로 이것이다.

 

i 도시에서 j 도시로 갈 수 없는 경우도 존재한다. 하지만 우리는 모든 도시를 돌아야 한다.

 

그럼 i 도시에서 j 도시로 못 가는 경우, 예를 들면 0 -> 1, 1 -> 2 만에 끝나는 경우가 있으면 이 것은 정답이 될 수 없다.

 

왜? 모든 도시를 방문하지 않았기 때문.

 

하지만 이 경우의 필터링을 해주지 않는다면 모든 도시를 방문하지 않아도 최소 값이 출력될 수 있다.

 

그러므로 이에 유의하자

정답 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int[][] map;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();

        map = new int[n][n];
        int[] country = new int[n];
        for (int i = 0; i < n; i++) {
            country[i] = i;
            for (int j = 0; j < n; j++) {
                map[i][j] = input.nextInt();
            }
        }
        int answer = Integer.MAX_VALUE;
        do {
            int sum = 0;
            boolean flag = false;
            for (int i = 0; i < country.length - 1; i++) {
                if(map[country[i]][country[i+1]] == 0) flag = true;
                else sum += map[country[i]][country[i+1]];
            }
            int value = map[country[country.length - 1]][country[0]];
            if(!flag && value != 0) {
                sum += value;
                answer = Math.min(answer, sum);
            }
        }while(nextPermutation(country));
        System.out.println(answer);
    }

    private static boolean nextPermutation(int[] arr) {
        int i = arr.length - 1;
        while(i > 0 && arr[i-1] >= arr[i]) i--;
        if(i <= 0) return false;

        int j = arr.length - 1;
        while(arr[i-1] >= arr[j]) j--;
        swap(arr, i-1, j);

        j = arr.length - 1;
        while(i < j) {
            swap(arr, i, j);
            i++;
            j--;
        }
        return true;
    }

    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.