[Java] SWEA / 최적경로 / 1247번

[Java] SWEA / 최적경로 / 1247번

문제

최적경로 문제 링크

문제의 저작권은 SW Expert Academy에 있습니다

접근 방식

1. 손님의 집 위치를 순열 배열로 만든다
2. 회사로부터 해당 배열의 손님 집을 지나 집으로 향하는 경로를 계산하여 최솟값을 저장한다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Solution_1247_정현명 {
	
	static int T,N;
	static int[] company;
	static int[] home;
	static int[][] customer;
	static int minPath;
	static int numbers[];
	
	public static void main(String[] args) throws IOException{
		
		// =================== 입력 ====================
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		T = Integer.parseInt(br.readLine());
		
		for(int tc=1;tc<=T;tc++) {
			N = Integer.parseInt(br.readLine()); // 고객 수
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			company = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())}; // 회사 위치
			home = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())}; // 집 위치
			
			customer = new int[N][2]; // 고객들 위치
			
			for(int i=0;i<N;i++) {
				customer[i] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
			}
			
			numbers = new int[N];
			minPath = 200 * 11; // 나올 수 없는 최대값  
			
			// ==================== 솔루션 ===================
			permutation(0,0);
			
			// ==================== 출력 =====================
			sb.append("#"+tc+" "+minPath+"\n");
		}
		
		System.out.print(sb);
	}
	
	
	// 순열 배열 만들기
	public static void permutation(int cnt, int flag) {
		if (cnt == N) {
			calPath(numbers); // 순열 배열이 만들어지면 해당 배열로 전체 경로길이 계산
			return;
		}
		
		for(int i=0;i<N;i++) {
			if((flag & 1<<i) != 0) continue;
			numbers[cnt] = i;
			permutation(cnt+1,flag | 1<<i);
		}
	}
	
	// 경로길이 계산
	public static void calPath(int numbers[]) {
		int r = company[1];
		int c = company[0];
		
		
		int sumPath = 0;
		for(int i=0;i<N;i++) {
			
			int nextR = customer[numbers[i]][1];
			int nextC = customer[numbers[i]][0];
			
			
			sumPath += Math.abs(nextR - r) + Math.abs(nextC - c);
			
			r = nextR;
			c = nextC;
		}
		sumPath += Math.abs(r - home[1]) + Math.abs(c - home[0]);
		
		minPath = Math.min(minPath, sumPath);
	}
	
}