[DP] TSP(외판원 순회)

www.acmicpc.net/problem/2098

2098번: 외판원 순회

DP 테크닉중 하나이다.

 

여기서 팁은

1->......->1

2->.....->2 

시작점이 어디던 시작점 -> 시작점으로 왔을때의 최솟값은 다 똑같다.

그래서 걍 1부터 시작해도 된다.

 

dp[][]을 생각하는게 여간 쉽지 않다. 복습이 많이 필요하다.

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210407_boj2098_외판원순회 {
 
    static int n;
    static final int INF = 987654321;
    
    static int arr[][];
    static int d[][];
    /* 제일 중요함!!!!!!!!
     d[node][visit] : 
     현재 node번에 있고 visit을 방문하고 왔을때 0번 노드로 가는 최소의 거리
     visit은 비트마스크이다.
     d[0][1] == 현재 0번 노드에 있고 0번 노드만 방문 하고 있는 상태일때 0번노드로 가는 최소의 거리.
     d[2][5] == 현재 2번 노드에 있고 0,2번 노드를 방문하고 있는 상태일때 0번 노드로 가는 최소의 거리.
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        arr = new int[n][n];
        d = new int[n][(1<<n)];
        
        for(int i = 0 ; i < n ; i++) {
            
        }
        
        for(int i = 0 ; i < n ; i++) {
            Arrays.fill(d[i], INF);
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < n ; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        //go(0,1) == d[0][1] => 16번째 줄을 보면 된다.
        System.out.println(go(0,1));
    }
    
    static int go(int cur_node, int visit) {
        
        if(visit == (1<<n)-1) {
            if(arr[cur_node][0] == 0)
                return INF;
            else
                return arr[cur_node][0];
        }
        
        if(d[cur_node][visit] != INF)
            return d[cur_node][visit];
        
        for(int i = 0 ; i < n ; i++) {
            
            //cur_node -> i 에 대한 길이 없다 || 이미 방문한 노드이면??
            if(arr[cur_node][i] == 0 || (visit & (1 << i)) != 0)
                continue;
            
            int n_visit = visit | (1<< i);
                                                    
            //만약 2번 노드를 다음것으로 쓰려면 arr[cur_node][2] + d[i][visit | (1<<2)]; 
            d[cur_node][visit] = Math.min(d[cur_node][visit], arr[cur_node][i] + go(i, n_visit));
        }
        
        
        return d[cur_node][visit];
    }
}

 

그런데

jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=817&sca=5050

JUNGOL

이 문제 때문에 java일 경우 탑다운이 안먹히는 경우가 있었다.

그래서 바텀업도 만들었다. (근데 당장에는 익히진 않을 것이다. 왜냐면 짜기 너무 어려움;;;;)

 

 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210407_jungol1545_해밀턴순환회로2_bottomup {
 
    static int n;
    static final int INF = 987654321;
    
    static int arr[][];
    static int d[][];
 
    public static void main(String[] args) throws IOException {
        
        //System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        arr = new int[n][n];
        d = new int[n][(1<<n)];
        
        
        for(int i = 0 ; i < n ; i++) {
            Arrays.fill(d[i], INF);
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < n ; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(i != j && arr[i][j] == 0)
                    arr[i][j] = INF;
            }
        }
        
        //d[0][1<<19 -1] 마지막이 0번노드이고 모든 정점을 방문했을때
        //d[0][1] 마지막이 0번노드이고 0번노드만 방문했을때 = 0
        //d[1][3] 마지막이 1번노드이고 0,1번 노드 방문했을때  = arr[0][1];
        //d[3][9] 마지막이 3번노드이고 0,3번 노드 방문했을때 = arr[0][3];
        
        d[0][1] = 0;
        for(int i = 1 ; i < n ; i++) {
            d[i][(1<<i) + 1] = arr[0][i];
        }
        
        // d[j][i] 에서 i는 0번노드는 무조건 방문상태여야 한다. 당연히 0번부터 시작했으니깐... 그래서 1 부터 +2를 하는 방식을 취했다.
        for(int i = 1 ; i < (1<<n)-1 ; i+=2) { // i는 visit. bitmask 전체를 훑는다.
            for(int j = 1 ; j < n ; j++) { // j 중간 경유 노드이다. 그런데 j = 0는 빼도 된다. 왜냐면 0번 노드는 이미 방문했으니깐...
                for(int k = 1 ; k < n ; k++) { // k는 마지막 방문 노드이다. 그런데 k = 0 는 빼도 된다. 왜냐면 0번 노드는 이미 방문했으니깐...
                    if((i & (1<<k)) != 0)
                        continue;
                    d[k][i+(1<<k)] = Math.min(d[k][i+(1<<k)], d[j][i] + arr[j][k]);
                }
            }
        }
        
        int ans = INF;
        
        for(int i = 1 ; i < n ; i++)
            ans = Math.min(ans, d[i][(1<<n) -1] + arr[i][0]);
        
        System.out.println(ans);
        
    }
}
/*
5
0 14 4 10 20 
14 0 7 8 7 
4 5 0 7 16 
11 7 9 0 2 
18 7 17 4 0
*/