해밀턴순회회로2 (정올 1545, 백준 2098)

해밀턴순회회로2 (정올 1545, 백준 )

전형적인 외판원순회 문제

두 문제의 n의 범위가 다르다. (정올: n<=20 백준: n<=16)

 

문제 링크

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=817&sca=99&sfl=wr_subject&stx=%ED%95%B4%EB%B0%80%ED%84%B4 

JUNGOL

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

2098번: 외판원 순회

 

풀이

외판원 순회 문제 (TSP) 이론

기본 논리는 같으나, 재귀를 이용한 코드는 n이 16 초과시 시간초과가 발생한다. 

핵심을 경로를 비트연산으로 처리하는 것 인거 같다. 

자바로는 c와 똑같은 방법으로 코딩해도 제한시간을 정말 아슬아슬 하게 통과한다. 400ms정도가 되는것이 정상이라는데 더 알아봐야할 것 같다.

 

코드

재귀사용

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

public class Main {
	static int INF = 16 * 1_000_000;//충분히 큰 수 but Integer.MAX_VALUE로 하면 초과가 발생하여 답이 나오지 않으니 주의
	static int n;
	static int[][] map;
	static int[][] dp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		n=Integer.parseInt(br.readLine());
		map=new int[n][n];
		dp=new int[n][(1<<n)-1];
		StringTokenizer st;
		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());
			}
			Arrays.fill(dp[i], INF);//초기화
		}//입력
		bw.append(tsp(0,1)+"\n");//0번째 노드,0번만 방문한 경로
		bw.flush();
		bw.close();
	}
	private static int tsp(int node, int vis) {
		if(vis==(1<<n)-1) {//모든 지점을 다 순회한 경우
			if(map[node][0]==0)return INF;//시작점으로 돌아가는 길이 없다.
			return map[node][0];
		}
		if(dp[node][vis]!=INF)return dp[node][vis];//이미 값이 있을경우
		for(int i=0;i<n;i++) {//i = 다음에 방문할 지점
			int next=vis|(1<<i);// 현재까지 경로에 i를 포함시킨 다음 경로
			if(map[node][i]==0||(vis&(1<<i))!=0)continue;//길이 없는 경우 or 새로 방문하고자 하는 지점i를 이전에 방문한 경우
			dp[node][vis]=Math.min(dp[node][vis], map[node][i]+tsp(i,next));//현재까지의 경로 vs i를 포함 시킨 새 경로
		}
		return dp[node][vis];//현재까지의 최단경로를 리턴한다.
	}
}

재귀 사용하지 않음

속도는 위에게 더 빠르다. n>17일때

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
	static int INF=987654321;
	static int n;
	static int[][] map;
	static int[][] dp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		n=Integer.parseInt(br.readLine());
		int m=(1<<n);
		map=new int[n][n];
		dp=new int[m][n];
		StringTokenizer st;
		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());
				if(map[i][j]==0)map[i][j]=INF;
			}
		}//입력
		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				dp[i][j]=INF;
			}
		}
		dp[1][0]=0;//초기화. 출발지에서의 비용은 0이다.
		for(int i=1;i<m-1;i+=2) {
			for(int j=0;j<n;j++) {
				for(int k=1,l=2;k<n;k++,l<<=1) {
					if((i&l)!=0)continue;//방문한 지점일때
					dp[i+l][k]=Math.min(dp[i+l][k], dp[i][j]+map[j][k]);//새로운 경로vs 기존 경로
				}
			}
		}
		int min=INF;
		for(int i=1;i<n;i++) {
			min=Math.min(min, dp[m-1][i]+map[i][0]);
		}//최소값 탐색
		bw.append(min+"\n");
		bw.flush();
		bw.close();
	}
}