[SWEA]1247번 최적 경로(JAVA)

0. 문제 링크

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

SW Expert Academy

 

1. 문제 설명

1) 회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 경로 찾기

 

2. 입출력

// input 
10 // 테스트 케이스의 개수
5 // 고객의 수
0 0 100 100 70 40 30 10 10 5 90 70 50 20 // 회사, 집, N명의 고객의 좌표
6
88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
10
39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36
...

// output
#1 200
#2 304
#3 366
...

 

3. 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class swea1247 {
	static int N;
	static int[][] map;
	static int[][] sel;
	static int[] com;
	static int[] home;
	static boolean[] v;
	static int ans;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			// 입력
			N = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			com = new int[2];
			com[0] = Integer.parseInt(st.nextToken());
			com[1] = Integer.parseInt(st.nextToken());
			home = new int[2];
			home[0] = Integer.parseInt(st.nextToken());
			home[1] = Integer.parseInt(st.nextToken());
			map = new int[N][2]; // 회사, 집, N명의 고객
			for (int i = 0; i < map.length; i++) {
				map[i][0] = Integer.parseInt(st.nextToken());
				map[i][1] = Integer.parseInt(st.nextToken());
			}
			ans = Integer.MAX_VALUE;
			
			// 회사 - N명의 고객 - 집 (순열)
			sel = new int[N][2];
			v = new boolean[N];
			recursive(0);
			
			System.out.printf("#%d %d\n", t, ans);
		}
		

	}
	private static void recursive(int idx) {
		// basis part
		if(idx == sel.length) {
			int temp = 0;
			temp += getDistance(com[0], com[1], sel[0][0], sel[0][1]);
			for(int i = 0; i < sel.length-1; i++) {
				temp += getDistance(sel[i][0], sel[i][1], sel[i+1][0], sel[i+1][1]);
			}
			temp += getDistance(home[0], home[1], sel[sel.length-1][0], sel[sel.length-1][1]);
			ans = Math.min(ans, temp);
			
			return;
		}
		
		// inductive part
		for(int i = 0; i < N; i++) { // 고객 거리만 구하면 됨
			if(v[i] == false) {
				v[i] = true;
				sel[idx][0] = map[i][0];
				sel[idx][1] = map[i][1];
				recursive(idx+1);
				v[i] = false;
			}
		}
	}
	
	private static int getDistance(int x1, int y1, int x2, int y2) {
		return Math.abs(x1-x2) + Math.abs(y1-y2);
	}

}

 

실행 결과

 

4. 회고

1) N개의 고객 좌표를 순서 O 중복 X 나열 -> 순열 

2) java.awt.Point를 이용하여 x, y를 한 객체로 표현할 수 있음

 

5. Github

https://github.com/iihye/Algorithm/blob/main/SWEA/swea1247.java