siio's blog

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

출력

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

예제 입력

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

예제 출력

35

접근 방법

1. 양의 가중치를 가지는 그래프에서 최소 비용으로 여행을 간다는 점을 보고 다익스트라를 먼저 떠올렸습니다.
2. 그러나 다익스트라는 하나의 출발지에서 다른 모든 도시까지의 최단 경로를 찾을 때에는 적합하지만, 모든 도시를 반드시 순회해야 하는 TSP 문제에는 적합하지 않습니다.
3. 따라서 모든 도시를 거치는 dfs와 모든 경로를 탐색해야 하므로 백트래킹을 사용하는 방법을 생각했습니다.
4. N의 크기가 최대 10까지이므로 완전탐색으로 문제를 풀 수 있을 것이라 판단했습니다.
   인접 행렬로 표현된 그래프의 DFS 시간복잡도 : O(V^2) (V: 정점의 개수)

주요 로직

1. 인접행렬로 그래프 표현

public static void init() throws Exception {
    N = Integer.parseInt(br.readLine());

    costs = new int[N][N];
    visit = new boolean[N];
    result = Integer.MAX_VALUE;

    for (int i = 0; i < N; i++) {
        String[] inputs = br.readLine().split(" ");
        for (int j = 0; j < N; j++) {
            costs[i][j] = Integer.parseInt(inputs[j]);
        }
    }
}

모든 도시를 순회하며 최소 비용 경로를 찾아야 하므로 이동 비용이 자주 조회될 것이라 생각하여 인접행렬로 그래프를 표현했습니다.

2. dfs + 백트래킹

public static void dfs(int node, int cnt, int sum, int start) {
    if(cnt == N) {

        // 순회가 되지 않는다면 패스
        if(costs[node][start] == 0) {
            return;
        }

        result = Math.min(result, sum + costs[node][start]);
        return;
    }

    visit[node] = true;

    for (int i = 0; i < costs[node].length; i++) {
        if (visit[i] || costs[node][i] == 0) {
            continue;
        }

        dfs(i, cnt + 1, sum + costs[node][i], start);
    }
    visit[node] = false;
}

도시를 DFS로 순회하며 경로를 탐색하고, 각 경로의 비용을 계산합니다. 경로가 완료되면 출발 도시로 돌아가는 비용을 더해 최소 비용을 갱신하고 백트래킹으로 모든 경로를 탐색합니다.

예를 들어, 0, 1, 2, 3 노드가 모두 각각의 노드에게 간선이 연결되어 있다고 가정해봅시다. 처음에는 0 → 1 → 2 → 3 -> 0 순으로 방문할 것이고 다음에는 0 → 1→ 3→ 2 -> 0 순으로 방문할 것입니다.

만약 cnt가 도시의 총 개수(N)와 같다면, 이는 모든 도시를 방문한 것이므로, 마지막 노드에서 출발 노드로 돌아가는 비용을 더해 결과를 갱신합니다. 이때 순회 경로가 만들어지지 않는다면 해당 경로는 무시합니다.

최종 코드

• 메모리 : 14996 kb
• 시간: 280 ms

import java.io.*;

public class BJ_S1_10971 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int[][] costs;
    static boolean[] visit;
    static int result;

    public static void main(String[] args) throws Exception {
        init();
        solve();
        output();
    }

    public static void output() {
        System.out.println(result);
    }

    public static void solve() {
        for (int i = 0; i < N; i++) {
            dfs(i, 1, 0, i);
        }
    }

    public static void dfs(int node, int cnt, int sum, int start) {
        if(cnt == N) {

            // 순회가 되지 않는다면 패스
            if(costs[node][start] == 0) {
                return;
            }

            result = Math.min(result, sum + costs[node][start]);
            return;
        }

        visit[node] = true;

        for (int i = 0; i < costs[node].length; i++) {
            if (visit[i] || costs[node][i] == 0) {
                continue;
            }

            dfs(i, cnt + 1, sum + costs[node][i], start);
        }
        visit[node] = false;
    }

    public static void init() throws Exception {
        N = Integer.parseInt(br.readLine());

        costs = new int[N][N];
        visit = new boolean[N];
        result = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                costs[i][j] = Integer.parseInt(inputs[j]);
            }
        }
    }
}