[백준] 외판원 순회3

문제 설명

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

문제 풀이

• 외판원 순회 문제는 다이나믹 프로그래밍을 사용하는 것이 정석이다.
• DP[현재노드][현재까지방문한노드의 비트마스킹값]
• 위 배열을 통해 메모이제이션을 진행하며 BFS를 진행하여 풀이하였다.

소스 코드 (JAVA)

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

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static class Point {
        int x, y;
        double z;

        public Point(int x, int y, double z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

    static int N;
    static Point[] arr;
    static double[][] map;

    static double[][] dp;


    public static void solve() throws IOException {
        double result = Double.MAX_VALUE;
        Queue<Point> q = new ArrayDeque<>();
        dp[0][1] = 0;
        q.add(new Point(0, 1, 0));
        while(!q.isEmpty()) {
            Point cur = q.poll();
            // 모든 지점을 방문했으면
            if (cur.y == ((1<<N) - 1)) {
                result = Math.min(result, cur.z + map[cur.x][0]);
                continue;
            }
            for (int i = 0; i < N; i++) {
                if (((1<<i) & cur.y) == (1<<i)) continue;
                double nDist = cur.z + map[cur.x][i];
                int nMask = cur.y + (1<<i);
                if (nDist > dp[i][nMask]) continue;
                dp[i][nMask] = nDist;
                q.add(new Point(i, nMask, nDist));
            }
        }
        bw.write(result + "\n");
    }


    static void init() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], Double.MAX_VALUE);
            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                map[i][j] = calDist(i, j);
            }
        }
    }

    static double calDist(int a, int b) {
        return Math.sqrt(Math.pow((double) arr[a].x - (double) arr[b].x, 2) + Math.pow((double)arr[a].y - (double)arr[b].y, 2));
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        map = new double[N][N];
        arr = new Point[N];
        dp = new double[N][1 << N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
        }
        init();
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bw.flush();
    }
}