[Jungol/Java] 1681. 해밀턴 순환회로

[Jungol/Java] 1681. 해밀턴 순환회로

JUNGOL

---

문제 해석

해밀턴 순환회로 문제는 모든 도시를 한 번씩 방문하고 출발점으로 돌아오는 경로 중 가장 비용이 적게 드는 순회 경로를 찾는 문제이다. 이 문제는 그래프의 표현에서 완전 그래프 형태로 제시되며, 각 도시 간의 이동 비용이 그래프의 간선으로 주어진다. 도시 간 이동할 수 없는 경우 비용이 0으로 표시된다.

풀이 과정

이 문제의 풀이는 백트래킹 기법과 비트마스킹을 사용하여 효율적으로 접근한다. 각 도시를 방문할 때마다 방문했음을 표시하기 위해 비트마스크를 사용하고, 경로의 비용 합이 현재까지 구한 최소 비용보다 클 경우 더 이상 진행하지 않고 되돌아간다(가지치기). 모든 도시를 방문한 후 출발 도시로 돌아올 수 있는지 확인하고, 가능하다면 총 이동 비용을 최소값과 비교하여 갱신한다.

코드

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

public class Main {
    int[][] graph;  // 그래프 배열
    int ans = Integer.MAX_VALUE;  // 최소 비용을 저장할 변수
    int[] sel;  // 방문한 도시를 저장할 배열

    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    private void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

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

        sel = new int[n];
        dfs(1, 0, 0);

        sb.append(ans);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void dfs(int k, int visited, int sum) {
        if (sum > ans) return;  // 현재 경로 비용이 최소 비용보다 크면 중단

        if (k == graph.length) {
            if (graph[sel[k-1]][0] == 0) return;  // 출발 도시로 돌아갈 수 없으면 중단
            sum += graph[sel[k-1]][0];  // 출발 도시로 돌아가는 비용 추가
            ans = Math.min(ans, sum);  // 최소 비용 갱신
            return;
        }

        for (int i = 1; i < graph.length; i++) {
            if ((visited & (1 << i)) == 0 && graph[sel[k-1]][i] != 0) {  // 방문하지 않았고, 이동 가능하면
                sel[k] = i;
                sum += graph[sel[k-1]][i];  // 비용 추가
                dfs(k + 1, visited | (1 << i), sum);  // 다음 도시 방문
                sum -= graph[sel[k-1]][i];  // 방문 취소
            }
        }
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 최악의 경우 O(n!)이다. 각 도시를 방문할 때마다 남은 도시들을 방문하는 모든 경우의 수를 고려하기 때문에, 도시의 수가 증가함에 따라 계산량이 팩토리얼로 증가한다.

느낀점

해밀턴 순환회로 문제는 NP-완전 문제로 알려져 있어, 효율적인 해결이 중요하다. 비트마스킹과 가지치기를 활용한 백트래킹 방식은 이러한 유형의 문제에서 계산량을 상당히 줄일 수 있어 매우 유용하다. 이번 풀이를 통해 보다 효과적인 문제 해결 방법과 최적화 기법에 대해 더 깊이 이해할 수 있었다.