[SWEA][JAVA] 1247 - 최적 경로

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE&problemTitle=1247&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

문제

 

 

 

설명

난이도 D5문제 치고는 그렇게 어려운 편은 아니긴 하나, 완전탐색 '순열' 아이디어를 못 잡고 어렵게 생각하는 바람에 좀 헤멨던 문제입니다.

순열 코드를 돌려서 각 경우의 결과에서 거리 계산을 한 다음, min값과 비교해서 최솟값을 업데이트시켜 주는 방식으로 풀었습니다.

이 문제는 정올 사이트 1681번(해밀턴 회로)와 비슷한 유형이지만, 정올 문제의 경우 시간제한이 1초이기 때문에 이 방식으로 풀면 시간초과가 날 것인데, 만약 풀어보신다면 이 점 참고해 주시면 좋을 것 같습니다. 정올 1681번 문제 포스팅은 올리는 대로 아래에 링크 걸어두겠습니다!

 

 

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class SWEA1247_OptimalPath {

	static class Position{
		int x, y;
		public Position(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static Position[] client; //고객 위치 배열
	static int N, minDistBtwClient;
	static Position[] result;
	static boolean[] isSelected;
	static Position company, home;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); //테스트 케이스 수
		
		for(int tc=1; tc<=T; tc++) {
			
			N = Integer.parseInt(br.readLine()); //고객의 수
			//초기화
			client = new Position[N];
			result = new Position[N]; 
			isSelected = new boolean[N]; 
		    minDistBtwClient=9999; 
		
			StringTokenizer st = new StringTokenizer(br.readLine());
			company = new Position(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); //회사의 위치
			home = new Position(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); //집의 위치
			
			for(int i=0; i<N; i++) {
				client[i] = new Position(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			} //입력 완료
			
			FindMinDistBtwClient(0); 
			System.out.println("#" + tc + " " + minDistBtwClient);
		}
	}
	
	public static void FindMinDistBtwClient(int cnt) {	//고객들 간의 최단 거리 리턴 -> 순열 사용
		
		if(cnt==N) { //순열 다 뽑았다면
			int distSum=0;
			
			for(int i=0; i<N-1; i++) { //각 고객 간의 거리
				Position c1 = result[i]; 
				Position c2 = result[i+1];
				int dist = Math.abs(c1.x - c2.x) + Math.abs(c1.y - c2.y);
				distSum += dist;
			}
			//"회사 - 고객 , 고객- 집" 거리 계산
			distSum += Math.abs(company.x - result[0].x) + Math.abs(company.y - result[0].y) + 
					Math.abs(home.x - result[N-1].x) + Math.abs(home.y - result[N-1].y);
			
			//min값 업데이트
			minDistBtwClient = Math.min(minDistBtwClient, distSum);
			return;
		}
		
		for(int i=0; i<N; i++) {
			
			if(isSelected[i])
				continue;
			isSelected[i]=true;
			result[cnt] = client[i];
			FindMinDistBtwClient(cnt+1);
			isSelected[i]=false;
		}
	}
}