[BOJ 10971] 외판원 순회 2 - Java (외판원 문제 TSP & 백트래킹 가지치기)

1. 문제 개요 및 조건 분석

항목	내용
문제 이름	외판원 순회 2 (백준 10971번 / 실버 2)
플랫폼 / 난이도	백준 (실버 2, 10971번)
문제 링크	백준 10971번
제한 사항	시간 제한 2초, 메모리 제한 256MB
입력 조건	도시 수 $N \le 10$, 비용 행렬 $W_{ij} \le 1,000,000$ ($W_{ij} = 0$은 갈 수 없음)
핵심 규칙	모든 도시를 거쳐 다시 출발 도시로 돌아오는 순회 여행 경로의 최소 비용 계산

---

2. 접근 아이디어: 외판원 순회(TSP) & 백트래킹 가지치기

순환 경로의 특성과 대칭성

• 순회 경로는 사이클(Cycle)이므로, 어느 도시에서 출발하든 결과는 동일합니다. 따라서 시작 도시를 항상 0번 도시로 고정해도 무방합니다.
• $N \le 10$이므로 전체 순열 경우의 수는 $(N - 1)! = 9! = 362,880$가지입니다.
• 가지치기 (Pruning):
  • 탐색 도중 현재 누적 비용 cost가 이미 기존에 구한 최솟값 minCost 이상이라면 더 이상 진행하지 않고 즉시 리턴합니다.

---

3. Java 풀이 코드

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

public class Main {
    static int n;
    static int[][] w;
    static boolean[] visited;
    static int minCost = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        w = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                w[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        visited = new boolean[n];
        visited[0] = true; // 0번 도시에서 출발 고정
        dfs(0, 0, 1);

        System.out.println(minCost);
    }

    static void dfs(int cur, int cost, int depth) {
        // 이미 최솟값 이상이면 가지치기
        if (cost >= minCost) return;

        // 모든 도시를 다 방문한 경우
        if (depth == n) {
            // 마지막 도시에서 시작점(0번)으로 돌아가는 경로가 있는 경우
            if (w[cur][0] > 0) {
                minCost = Math.min(minCost, cost + w[cur][0]);
            }
            return;
        }

        for (int next = 0; next < n; next++) {
            if (!visited[next] && w[cur][next] > 0) {
                visited[next] = true;
                dfs(next, cost + w[cur][next], depth + 1);
                visited[next] = false;
            }
        }
    }
}

---

4. 복잡도 분석

• 시간 복잡도: $O((N - 1)!)$ — $N = 10$에서 약 36만 회 연산이며, 강력한 가지치기로 실제 연산은 수만 번 이내로 0.1초 미만에 즉시 통과.
• 공간 복잡도: $O(N^2)$ — 비용 행렬 및 방문 배열.

---

5. 채점 결과 및 통과 인증