[SW Expert Academy Java] 1247 S/W 문제해결 응용 3일차 - 최적 경로

 

문제

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD 

SW Expert Academy

 

 

 

 

돌아오는 경로 중 가장 짧은 것을 찾아야 하기 때문에 최솟값을 구한다.

문제의 아래에 힌트가 있다. '모든 가능한 경로를 살펴서 해를 찾아도 좋다.'->순열로 문제를 해결해도 좋다.

고객의 수가 최대 10명이기 때문에, 시간복잡도가 최대 10!이 나온다. 따라서 순열로 풀이가 가능하다.

풀이방법

---

• 입력받은 후 순열을 구해준다.
• 뽑힌 값이 n이 된다면 count를 세어준다.
• count는 회사와 첫번째 사람들과의 거리, N명의 사람들간의 거리, 마지막 사람과 집과의 거리를 구해준다.
• 최솟값을 갱신한다.

코드

---

 

 

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

public class Solution_1247{

	static int[][] people; //n명의 고객 배열
	static int[][] direct; //순열로 뽑은 고객들을 넣어줄 배열
	static boolean[] visited; //방문한 집인지 확인할 배열
	static int hx,hy,cx,cy,n,total;
	static int count; //거리
	static int min=Integer.MAX_VALUE; //최종 출력값
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		input.nextInt();
		for(int t=0; t<10; t++) {
			min=Integer.MAX_VALUE;
			n=input.nextInt();
			cx=input.nextInt(); //회사의 좌표
			cy=input.nextInt();
			hx=input.nextInt(); //집의 좌표
			hy=input.nextInt();
			
			people=new int[n][2]; //N명의 고객좌표
			for(int i=0; i<n; i++) {
				people[i][0] = input.nextInt(); //고객의 x좌표
				people[i][1] = input.nextInt(); //고객의 ㅛ좌표
			}
			
			direct=new int[n][2];
			visited=new boolean[n];
			perm(0);
			System.out.printf("#%d %d",t+1,min);
			System.out.println();
		}

	}
	
	static void perm(int cnt) {
		count=0;
		if(cnt==n) {
			count=Math.abs(cx-direct[0][0])+Math.abs(cy-direct[0][1]); //회사와 첫번째 사람과의 거리
			for(int i=0; i<n-1; i++) {
				count+=Math.abs(direct[i][0]-direct[i+1][0])+Math.abs(direct[i][1]-direct[i+1][1]);
                //N명의 사람들과의 거리
			}
			count+=Math.abs(hx-direct[n-1][0])+Math.abs(hy-direct[n-1][1]);//마지막 사람과 집과이 거리
			min=Math.min(count,min); //최소값 갱신
			return;
		}
		for(int i=0; i<n; i++) {
			
			if(visited[i]==false) {
				direct[cnt][0]=people[i][0];//방문할 집들 뽑기
				direct[cnt][1]=people[i][1];
				visited[i]=true;
				perm(cnt+1);
				visited[i]=false;
			}
			
		}
		
	}

}