[백준 Gold 1] 2098 외판원 순회 - Java

문제링크 : https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

접근 과정 : 

• 백준 10971 외판원순회2 문제의 코드를 리팩토링 시키는 방향으로 시도해보았다.
• 완전탐색으로 모든 경우를 탐색하면 시간초과!!
• 즉, 메모리제이션을 통해 이전에 체크한 부분을 재활용해야 한다.
• DP[][]을 만들어서 이를 관리
• i 도시에 있고 j 비트에 포함된 도시를 탐색한 상황에서, 남은 도시를 모두 방문하는 최소비용
• 또한, 결국 하나의 사이클을 구하는 것이기에, 어디서 출발하든 상관이 없다.!!!

 

소스 코드 및 결과 :

package BOJ;

/* 
    외판원 순회 

*/

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

public class BOJ2098 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        dp = new int[N][(1 << N)];

        INF = 20000000;
        Arrays.fill(dp[0], INF);
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], INF);
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(travel(0, 1));

    }

    static int N, INF;
    static int[][] map;
    static int[][] dp; // i도시에 있고, j비트에 포함된 도시들을 방문했을 때, 남은 도시 방문의 최소비용

    static int travel(int now, int visit) {

        if (visit == (1 << N) - 1) {
            if (map[now][0] == 0) {
                return INF;
            }
            return map[now][0];
        }
        
        if (dp[now][visit] != INF) {
            return dp[now][visit];
        }

        for (int i = 0; i < N; i++) {
            if (map[now][i] == 0 || (visit & (1 << i)) != 0) {
                continue;
            }

            dp[now][visit] = Math.min(dp[now][visit], travel(i, visit | (1 << i)) + map[now][i]);
        }

        return dp[now][visit];
    }
}

 

P.S 

- 사이클이기에 출발 도시 상관없이 한번만 시도하면 되는것.!!

- 비트를 이용한 DP 활용.

이 두개가 주요 관건이었던것 같다.