자바 - 백준 2098 / 외판원 순회

https://www.acmicpc.net/problem/2098

골드1

구현 방법

1. 도시수 범위: 2이상 16이하
2. 단방향 → 두 도시간 이동 비용은 대칭 아님
3. 모든 도시간 비용은 양의 정수
4. 모든 도시를 방문하고 처음 도시로 돌아오는 최소 비용
5. 방문 했던 도시는 재방문 불가능

5가지의 조건을 통해 전형적인 TSP 문제임을 알 수 있습니다.

해당 문제를 완전 탐색으로 풀 경우 O(N!)의 시간복잡도를 가집니다.

따라서 비트마스크와 DP를 활용하여 시간 복잡도를 줄여야 합니다.

이 방식을 통해 O(N * N * 2^N)으로 줄일 수 있습니다.

비트마스크

• 방문 상태 표현

DP 테이블 정의

• dp[도시 수][비트마스크] = 이동 비용

DP 점화식

• W[i][j]: 도시 i에서 도시 j로 이동하는 비용
• dp[j][visited∣(1<<j)]=min(dp[j][visited∣(1<<j)],dp[i][visited]+W[i][j])

 

다익스트라 알고리즘이 안되는 이유

• 다익스트라의 경우, 출발점에서 도착점까지 최단 경로를 찾는 알고리즘 입니다. 즉, 모든 도시를 방문하는 경우에 대한 판단은 불가능 합니다.

 

프림 알고리즘이 안되는 이유

• 프림의 경우, 최소 스패닝 트리를 구하는데 사용됩니다. 따라서 모든 도시를 방문하지만, 다시 출발점으로 돌아오는 부분에 대한 판단을 할 수 없습니다. 왜냐하면 프림 알고리즘의 전제는 사이클이 없는 경우, 즉 트리인 상황만 고려하기 때문입니다.

코드

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

/**
* 백준 2098
* 외판원 순회
* 골드 1
* https://www.acmicpc.net/problem/2098
*/
public class Boj2098 {

    static final int INF = 17_000_000;

    static int N; //도시 수
    static int[][] w; //비용
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        dp = new int[N][1 << N];
        for(int i = 0; i < N; i++)
            Arrays.fill(dp[i], -1);


        System.out.println(tsp(0, 1));
    }

    public static int tsp(int cur, int visited) {
        if(visited == (1 << N) - 1) {

            return w[cur][0] == 0 ? INF : w[cur][0];
        }

        // 이미 방문한 적이 있다.
        if(dp[cur][visited] != -1)
            return dp[cur][visited];

        // 방문 했다는 표시
        dp[cur][visited] = INF;

        for(int i = 0; i < N; i++) {
            int next = visited | (1 << i);

            // 가는 경로가 없는 경우, 이미 방문 했을 경우
            if(w[cur][i] == 0 || (visited & (1 << i)) != 0)
                continue;

            dp[cur][visited] = Math.min(dp[cur][visited], w[cur][i] + tsp(i, next));
        }

        return dp[cur][visited];
    }

}