[삼성 SW Expert Academy] 1247. 최적 경로

 

Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE 

SW Expert Academy

 

import java.util.Arrays;
import java.util.Scanner;

public class 최적경로 {

	// 순열 사용
	static int [] client ;  
	static int N;
	static boolean check[] ;
	static int sel[] ;
	static int distance, answer ; // 총 거리 
	static int company_x, company_y, home_x, home_y;
	
	static void perm(int idx ) {
		
		// 기저 조건
		if ( idx == N*2 ) {
			// System.out.println(Arrays.toString(sel));
			
			// 순열이 결정 되었을 때, 회사 - 고객 - 집 거리를 구하자 거리 공식 : |x1-x2| + |y1-y2|
			
			// 회사 - 첫번 째 거리
			distance = Math.abs(company_x-sel[0]) + Math.abs(company_y-sel[1]);
			// 고객 간 거리
			for ( int i=0; i<N*2-2; i += 2) {
				distance += Math.abs(sel[i+2]-sel[i]) + Math.abs(sel[i+3]-sel[i+1]);
				
			}
			// 고객 - 집 거리
			distance += Math.abs(home_x-sel[N*2-2]) + Math.abs(home_y-sel[N*2-1]);
			
			// 최단 거리 저장
			if ( answer > distance) answer = distance;
			
			
			return;
		}
		
		// 조건은 짝수만 이용하자 
		
		for ( int i=0; i< N*2 ; i += 2) {
			if ( !check[i]) { // 선택되지 않은 값에 대해서
				check[i] = true; // 선택할거야!
				sel[idx] = client[i];  // 첫번째 고객의 x 좌표 
				sel[idx +1 ] = client [ i + 1]; // 첫번째 고객의 y좌표
				perm(idx+2);
				check[i] = false; // 되돌리기 
			}
		}
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int Tc = sc.nextInt(); // test case
		
		for ( int tc = 1; tc <= Tc; tc ++) {
			
			N = sc.nextInt(); // 고객의 수 입력받기
			company_x = sc.nextInt(); // 회사의 x 좌표
			company_y = sc.nextInt(); // 회사의 y 좌표
			
			home_x = sc.nextInt(); // 집의 x 좌표
			home_y = sc.nextInt(); // 집의 y 좌표
			
			// 초기화
			answer = Integer.MAX_VALUE;
			distance =0;
			
			client = new int[N*2]; // 고객의 x, y 좌표 생성
			check = new boolean[N*2]; // 사용 여부 체크  
			sel = new int[N*2]; // 선택된 값 
			
			for ( int i=0; i< N*2; i++) {
				client[i] = sc.nextInt();  // 고객의 , y 좌표 저장				
			}
			
			// 순열 호출 => 각 고객의 좌표를 출력 or 저장 해보자.
			perm(0);
			// 출력된 좌표를 활용해 회사 - 고객 좌표 - 집 거리를 구해보자 
			
			
			
			System.out.println("#"+tc+" "+ answer);
		}
		
		sc.close();
	}

}

 풀이 방법 팁 : 순열 ( 재귀 함수 ) 을 사용.

 

 1) 고객의 집을 입력받아 모든 순열로 나열하는 테스트

 2) 회사 - 첫번 째 고객의 집 거리 

 3) 고객 집 간의 거리 

 4) 마지막 고객 집 - home 거리 

 5) 모든 거리의 합 중 최단 거리를 출력