Notice
Recent Posts
Link
- Today
- Total
hye-log
[SWEA]1247번 최적 경로(JAVA) 본문
0. 문제 링크
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD
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
728x90
'CodingTest > SWEA' 카테고리의 다른 글
[SWEA]1228번 암호문1(JAVA) (0) | 2023.08.08 |
---|---|
[SWEA]1209번 Sum(JAVA) (0) | 2023.08.07 |
[SWEA]1225번 암호생성기(JAVA) (0) | 2023.08.07 |
[SWEA]1218번 괄호 짝짓기(JAVA) (0) | 2023.08.07 |
[SWEA]6808번 규영이와 인영이의 카드게임(JAVA) (0) | 2023.08.06 |
Comments