[SWEA] 최적 경로 (Java 자바)

풀이 및 소스코드

 

메소드 이름을 잘못지었다.

조합이아니라 순열이기 때문 ㅠ ㅠ ㅠ ... 

순열을 만들면서 그때그때 거리의 합을 구해준다.

만약 현재의 합이 저장된 최단거리보다 커지면 그냥 return 해줌으로써 시간을 단축할 수 있다.

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

public class Solution {
	static int n;
	static XY start, end;
	static ArrayList<XY> point;
	static int[] v;
	static boolean[] select;
	static int res;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= t; tc++) {
			n = Integer.parseInt(br.readLine());
			v = new int[n]; // 방문 표시할 int 배열
			select = new boolean[n];
			res = Integer.MAX_VALUE;// 최단거리를 구해야하므로 최댓값으로 초기화
			point = new ArrayList<>();
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			start = new XY(x, y);
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			end = new XY(x, y);
			for (int i = 0; i < n; i++) {
				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());
				point.add(new XY(x, y)); // 추가하기
			}

			combi(start , 0, 0);

			sb.append("#").append(tc).append(" ").append(res).append("\n");

		}
		System.out.println(sb);
	}

	public static int cal_dist(XY a, XY b) {
		return (Math.abs(a.x - b.x) + Math.abs(a.y - b.y));
	}

	public static void combi(XY nowxy, int cnt, int sum) {
		if (cnt == n) {
			// 회사까지간거까지 해서 한번더 비교
			sum = sum + cal_dist(nowxy, end);
			res = Math.min(sum, res);
			return;
		}
		if (res <= sum)
			return;
		for (int i = 0; i < n; i++) {
			if (select[i]) //이미 선택되었다면 패스
				continue;

			select[i] = true;
			combi(point.get(i), cnt + 1, sum + cal_dist(nowxy, point.get(i)));
			select[i] = false;
		}
	}
}

class XY {
	int x;
	int y;

	public XY(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}