[BOJ] 2098번 외판원 순회 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static final int INF = (int) 1e9;
    static int N;
    static int[][] map, dp;

    public static void main(String[] args) throws IOException {
        init();
        print();
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine());
        // 도시 연결 정보 입력
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 최단거리 테이블 초기화(-1 : 미방문)
        dp = new int[N][1 << N];
        for (int i =0; i < N ; i++) {
            Arrays.fill(dp[i], -1);
        }
    }

    private static void print() {
        System.out.println(tsp(0, 1));
    }

    private static int tsp(int now, int visited) {

        // 모든 도시를 방문한 경우
        if (visited == ((1 << N) - 1)) {
            if (map[now][0] == 0) return INF;
            return map[now][0];
        }

        /* 아래와 같이 처리를 안해주면 58%에서 시간초과 발생 */
        // 이미 방문한 경우 수행하지 않음
        if (dp[now][visited] != -1) return dp[now][visited];
        // 방문처리
        dp[now][visited] = INF;

        for (int i = 0; i < N; i++) {
            // 이미 방문했으면 처리 X
            if (map[now][i] == 0 || (visited & (1 << i)) != 0) continue;
            // dp[i][j] : 현재 있는 도시가 i이고, 지금까지 방문한 도시들의 집합이 j 일 때
            // 방문하지 않은 다른 도시들을 모두 방문한 뒤 돌아오는 최소 비용
            // 현재 최솟값과 다음도시를 방문한 결과와의 최솟값 비교
            dp[now][visited] = Math.min(dp[now][visited], tsp(i, visited | (1 << i)) + map[now][i]);
        }
        return dp[now][visited];
    }
}

📄 해설

• 외판원 순회의 대표 문제
• 외판원 순회 알고리즘을 사용해서 해결하면 되는 문제로, 외판원 순회 알고리즘에 대한 설명은 작성자의 글을 참고해도 좋고, 그냥 검색해서 나오는 글을 참고해도 좋음
  작성자의 글(작성 중)
• N 이 16이하이므로, DP 와 비트마스킹을 사용하여 풀어야하는 문제
  • DP 테이블 : DP[현재 도시][방문한 도시] = 나머지 도시들을 방문하는데 드는 최소비용
  • 비트마스킹 : DP 테이블에서의 방문한 도시를 표현할 때 사용
    • 방문한 도시의 비트는 1, 방문하지 않은 도시의 비트는 0 으로 표시
• 방문처리를 할 때, dp 테이블의 값이 INF 인 경우로 해주어서 58% 쯤에서 계속해서 시간 초과가 발생하였음. 미방문 지점은 -1 처리를 해야함