1247(最適なパス)
23452 ワード
質問元:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD社と家、顧客の距離情報を含む配列図を作成する. 社と家の順番が決まっているので、顧客間の距離を並べ替えることで、すべての場合の数を作り出し、最初と最後の距離に会社と家の距離を加えて、最高値を探します. 種の打法で使用後追跡できますが、適切な方法が思いつかず、時間は減っていません...😥
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine()); // 테케 갯수
StringBuilder sb = new StringBuilder();
int problemNum = 1;
while (T-- > 0) {
int N = Integer.parseInt(reader.readLine()); // 고객의 수
int[][] value = new int[N + 2][2];
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
for (int i = 0; i < N + 2; i++) {
for (int j = 0; j < 2; j++) {
value[i][j] = Integer.parseInt(tokenizer.nextToken());
}
}
int min = Integer.MAX_VALUE;
int[] index = new int[N];
for (int i = 0; i < N; i++) {
index[i] = i + 2;
}
do {
// 출발은 회사
// 도착은 집
int sum = 0;
// 회사에서 첫 번째 고객까지의 거리
sum += Math.abs(value[index[0]][0] - value[1][0]) + Math.abs(value[index[0]][1] - value[1][1]);
for (int i = 1; i < index.length; i++) {
sum += Math.abs(value[index[i]][0] - value[index[i - 1]][0]) + Math.abs(value[index[i]][1] - value[index[i - 1]][1]);
if (sum > min) break;
}
// 마지막 고객에서 집까지의 거리
sum += Math.abs(value[index[index.length - 1]][0] - value[0][0]) + Math.abs(value[index[index.length - 1]][1] - value[0][1]);
min = Math.min(min, sum);
} while (np(index));
sb.append("#").append(problemNum++).append(" ");
sb.append(min).append("\n");
}
System.out.println(sb);
}
private static boolean np(int[] arr) {
int lastIndex = arr.length - 1;
int i = lastIndex;
while (i > 0 && arr[i - 1] >= arr[i]) i--; // arr[i - 1] < arr[i]가 되면 탈출한다.
if (i == 0) return false; // 내림차순으로 정렬이 다 된 경우
int j = lastIndex;
while (arr[i - 1] >= arr[j]) j--; // arr[i - 1] < arr[j]가 되면 탈출한다.
swap(arr, i - 1, j);
int k = lastIndex;
while (i < k) swap(arr, i++, k--);
return true;
}
private static void swap(int[] arr, int from, int to) {
int temp = arr[from];
arr[from] = arr[to];
arr[to] = temp;
}
}
Reference
この問題について(1247(最適なパス)), 我々は、より多くの情報をここで見つけました https://velog.io/@ghc1124/SW-Expert-Academy-1247번최적-경로テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol