[백준 2098] 외판원 순회 (Java)

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

2098번: 외판원 순회

1. 주의할 점

- 메모아이즈(DP) + 비트마스크를 통해 해결한다

- 순회 만족 조건은?

 

2. 구현

- 비용에 대한 정보를 Arr[][] 배열에 담는다

- Check[Cur][Val] 배열을 통해 Cur 도시에 도착할 때 방문했던 도시번호들의 합을 Val이라고 한다. 이 때, 비용의 최소값을 저장한다

- 순회가 된다면, 어떤 Node에서 시작해도 상관없기 때문에 0번에서 시작한다(순회 만족 조건)

- Dfs() 함수를 통해 순회의 최소 비용을 구하며, Knum은 현재까지 방문한 도시번호들의 합이다

- 이미 Check[][] 값을 갱신했다면, Check[][] 값을 반환한다

- 연결되어 있지 않거나 자기 자신으로 돌아가려는 경우는 Continue. 또한, 이미 방문한 Node인 경우 Continue를 수행한다

 

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

class Main {
    static final int maxi = 987654321;
    static int check[][],arr[][];
    static int num,result;
    
    static int dfs(int cur, int knum){
        if(knum == ((1<<num)-1))   return 0;    //순회 완료
        int ret = check[cur][knum];
        if(ret!=maxi) return ret;
        for(int i=0;i<num;i++){
            int nv = arr[cur][i];
            if(nv==0 || cur==i) continue;     //연결되어 있지 않은 경우 or 자기자신
            int nk = knum|(1<<i);
            if(nk==knum || (i==0 && nk!=((1<<num)-1))) continue;      //이미 방문한 Node
            int vv = nv+dfs(i,nk);
            ret = Math.min(ret,vv);
        }
        return check[cur][knum] = ret;
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    num = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    result=maxi;
	    arr = new int[num][num];
	    check = new int[num][(1<<num)];
	    for(int i=0;i<num;i++)
	        for(int k=0;k<(1<<num);k++)
	            check[i][k]=maxi;
	    
	    for(int i=0;i<num;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        for(int j=0;j<num;j++){
	            int val = Integer.parseInt(st.nextToken());
	            arr[i][j]=val;
	        }
	    }
	    result = dfs(0,0);
	    
		System.out.print(result);
	}
}