10971번: 외판원 순회 2

문제

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있습니다. 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 경로를 계획하려고 합니다. 단, 한 번 갔던 도시로는 다시 갈 수 없습니다. (맨 마지막에 출발 도시로 돌아오는 것 제외) 각 도시간 이동 비용이 주어졌을 때, 가장 적은 비용이 드는 순회 경로를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 도시의 개수 N (2 ≤ N ≤ 10), 비용 행렬 W (비용은 1,000,000 이하, 갈 수 없는 경우 0)
• 출력: 외판원의 순회에 필요한 최소 비용

핵심 최적화: 시작점 고정

이 문제는 모든 도시를 방문하고 다시 처음으로 돌아오는 사이클(Cycle)을 찾는 문제입니다. 순회 경로가 0 → 1 → 2 → 3 → 0인 경우, 1번에서 시작하든 2번에서 시작하든 거치는 경로와 총비용은 동일합니다. 따라서 모든 도시를 시작점으로 잡아 탐색할 필요 없이, 0번 도시(혹은 임의의 한 도시)를 시작점으로 고정하여 탐색해도 모든 가능한 사이클을 확인할 수 있습니다. 이를 통해 연산량을 N배 줄일 수 있습니다.

풀이: 매개변수를 활용한 백트래킹 탐색

• 상태 전달: 재귀 함수 go에 현재 위치(now), 누적 비용(sum), 방문한 도시 수(cnt)를 매개변수로 전달하여 상태를 관리합니다.
• 가지치기 (Pruning): 탐색 도중 현재까지의 누적 비용(sum)이 이미 기존에 찾은 최소 비용(ans)보다 크거나 같다면, 더 이상 탐색할 필요가 없으므로 즉시 종료합니다.
• 기저 조건: 모든 도시를 방문했을 때(cnt == n), 현재 도시에서 시작 도시(start)로 돌아갈 수 있는 길이 있는지 확인하고(w[now][start] != 0), 있다면 최종 비용을 합산하여 최솟값을 갱신합니다.

코드

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

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

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       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];

       // 사이클을 찾는 문제이므로 시작점을 0으로 고정해도 무방함
       visited[0] = true;
       go(0, 0, 0, 1);

       bw.write(ans + "");
       bw.flush();
    }

    /**
     * @param start 시작 도시 (마지막에 복귀하기 위함)
     * @param now 현재 위치한 도시
     * @param sum 현재까지 누적된 이동 비용
     * @param cnt 지금까지 방문한 도시의 수
     */
    static void go(int start, int now, int sum, int cnt) {
       // 가지치기: 이미 최솟값을 넘었다면 중단
       if (sum >= ans) {
          return;
       }

       // 모든 도시를 순회한 경우
       if (cnt == n) {
          // 마지막 위치에서 다시 시작점으로 돌아갈 수 있는지 확인
          if (w[now][start] != 0) {
             ans = Math.min(ans, sum + w[now][start]);
          }
          return;
       }

       for (int i = 0; i < n; i++) {
          // 아직 방문하지 않았고, 현재 도시에서 갈 수 있는 경로가 있는 경우
          if (!visited[i] && w[now][i] != 0) {
             visited[i] = true;
             go(start, i, sum + w[now][i], cnt + 1);
             visited[i] = false; // 백트래킹 (방문 해제)
          }
       }
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force), 백트래킹 (Backtracking), 외판원 순회 문제 (TSP)