(Baekjoon) dp - (3) 외판원 순회

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

2098번: 외판원 순회

 

우선 외판원 문제는 현재 나온 이론으로는 풀수없지만

그나마 가장 나은 방법으로 푸는것이 DP방법이다라는 사실을 알고있어야한다.

N! 를 n^2*2^n 으로 줄였다는 사실만 알자.

 

비트마스크 복습

 

 

dp[3][1011] 의 뜻은 3번째도시에서           2 번째도시까지 가는 최소한의 수

dp[2][111]  의 뜻은 2번째도시에서            3 번째도시까지 가는 최소한의 수

dp[1][11]    의 뜻은 1번째도시에서 2,3 or 3,2 번째도시까지 가는 최소한의 수

dp[0][1]     의 뜻은  0번째도시에서 2,3,4 or 2,4,3 or ... 번째 도시까지는 가는 최소한의 수

 

결국은 tsp를 재귀적으로 수행하면서 

이러한과정중에

1. 최솟값을 dp에 넣고

2. 해당 dp가 다음번에도 있다면 재조사없이 그대로 갔다 쓰면서

동적으로 프로그래밍이 진행된다.

 

 

 

 

 

 

 

package dp;

import java.io.IOException;
import java.util.Scanner;

public class _2098 {
    static int map[][] =new int[16][16];
    static int dp[][] = new int[16][1<<16]; // [16][65536]
    static int n,visited;
    static int INF = Integer.MAX_VALUE - 1000000;

    // visited : 내가 어디에 방문했는지 확인해보는 함수
    static int tsp(int current, int visited){

        if((visited == (1 << n) - 1 )){
            if(map[current][0] == 0){
                return INF;
            }
            return map[current][0];
        }

        if(dp[current][visited] != 0 ){
            return dp[current][visited];
        }
        
        dp[current][visited] = INF;

        for(int k = 0 ; k < n ; k++){
            int next = 1 << k;
            if(map[current][k] == 0 || (visited & next) > 0){
                continue;
            }

            dp[current][visited] = Math.min(dp[current][visited], tsp(k, visited | next) + map[current][k]);

        }

        return dp[current][visited];

    }

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

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(sc.next());
            }
        }
        

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

}

이론만 가진상태에서 재귀함수를 사용하여 이걸 작성한 사람은 몇명이나 될까 생각이든다.

이런코드는 너무 이해가 안가서 공부하다보니까 어쩔수없이 외우는 코드같다.

그래도 재미있는 문제같다.

 

 

 

원본코드 : https://github.com/hotehrud/acmicpc/blob/master/algorithm/bitmask/2098.java

hotehrud/acmicpc

코드제작자블로그 참고 : https://mygumi.tistory.com/361

비트마스크(BitMask) 는 무엇인가? :: 마이구미

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study