[백준 *Java] - 외판원 순회2(10971)

외판원 순회2

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로 가기 위한 비용을 나타낸다.

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

출력

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

---

👇 접근 방식(내 생각 정리)

순열을 먼저 생각해서, 그림 그리면서 풀었습니다

처음에 인풋값을 다 받아 저장한 뒤, 행렬을 생각해서 for문을 돌면서 행렬 i, j에 있는 input 값을 가져와서 더해주는 형식으로 진행했습니다. 

하지만,

이게, 먼저 비용이 0원인 지를 확인한 뒤에 탐색을 했어야 했는데,

그게 아니라, 행렬을 다 돌고, 비용을 가져와서 더해주는 식으로 로직을 구하다보니, 만약 i에서 j로 갈 경우에 0이라는 숫자로 가지 못하는 상황이 있을 수 있습니다.

이 예외를 잡아주었더니 맞게 나오긴했습니다

하지만, 시간 복잡도가 높게 나와 코드를 수정해야할 거 같습니다...

 

 

아래는 성공한 코드입니다. 시간복잡도가 좀 높게 나온 지라, 코드 수정을 해야할 거 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] arr;
    static int[][] inputDataArr;
    static boolean[] visited;
    static int minCost = Integer.MAX_VALUE;
    static void backTracking(int depth) {

        if (N == depth) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                int a = arr[i] - 1;
                int b;
                
                if (i == arr.length-1) b = arr[0] - 1;
                else b = arr[i + 1] - 1;
                
                if (inputDataArr[a][b] == 0) return;
                else sum += inputDataArr[a][b];
            }
            minCost = Math.min(minCost, sum);
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i + 1;
                backTracking(depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        inputDataArr = new int[N][N];
        visited = new boolean[N];
        
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                inputDataArr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        backTracking(0);
        System.out.println(minCost);

    }
}