[swexpert] 1247. 최적 경로 (TSP, 외판원순환 문제, JAVA)

swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

모든 곳을 방문하는 여러 경로 중 가장 짧은 거리를 구하는 문제

 

이 문제는 시간 초과를 내지는 않는 문제 같아서 그냥 DFS 돌리면 되는데 visit배열 대신 비트마스크를 썼다. 

 

 

import java.util.ArrayList;
import java.util.Scanner;

public class Solution {

	static int n,t;
	static ArrayList<Integer[]> pos;
	static Integer[] home;
	static int dis=Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			dis=Integer.MAX_VALUE;
			pos=new ArrayList<Integer[]>();
			pos.add(new Integer[] {sc.nextInt(),sc.nextInt()}); //회사 좌표
			home=new Integer[] {sc.nextInt(),sc.nextInt()}; //집 좌표는 따로 넣어줌
			for (int i = 0; i < n; i++) { //n개의 고객위치를 넣어주고 
				pos.add(new Integer[] {sc.nextInt(),sc.nextInt()});
			}
			pos.add(new Integer[] {home[0],home[1]}); //가장 마지막에 집의 좌표 넣어준다.
			check(0,0,0,0);
			System.out.printf("#%d %d\n",tc,dis);
		}
		
		
	}

	private static void check(int idx,int prev,int cur_dis,int flag) { //개수,전의 위치,현재까지 거리,비트마스크(visit)
    
//		방문하는 마을은 n개이다.
		if(idx==n) {
			cur_dis+=getDistance(prev,n+1);
			if(dis>cur_dis)dis=cur_dis;
			return;
		}
//		시작은 회사에서부터 (0), 고객은 1~n, 집은 n+1
		for (int i = 1; i < n+1; i++) {
			if((flag&1<<i)!=0)continue; //방문한 곳은 pass
            //방문하지 않았다면 새로 거리를 더해주고 visit도 추가해주며 현재위치를 넘겨준다.
			check(idx+1,i,cur_dis+getDistance(prev,i),flag|1<<i);
		}
		
	}
	
	private static int getDistance(int a,int b) {
		int dis=0;
		dis=Math.abs(pos.get(a)[0]-pos.get(b)[0])+Math.abs(pos.get(a)[1]-pos.get(b)[1]);
		return dis;
	}

}