문제
삼성전자의 서비스 기사인 김대리는 회사에서 출발하여 냉장고 배달을 위해 N명의 고객을 방문하고 자신의 집에 돌아가려한다.
회사와 집의 위치, 그리고 각 고객의 위치는 이차원 정수 좌표 (x, y)로 주어지고 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100)
두 위치 (x1, y1)와 (x2, y2) 사이의 거리는 |x1-x2| + |y1-y2|으로 계산된다.
여기서 |x|는 x의 절대값을 의미하며 |3| = |-3| = 3이다. 회사의 좌표, 집의 좌표, 고객들의 좌표는 모두 다르다.
회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 한다.
회사와 집의 좌표가 주어지고, 2명에서 10명 사이의 고객 좌표가 주어질 때,
회사에서 출발해서 이들을 모두 방문하고 집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾는 프로그램을 작성하라.
여러분의 프로그램은 가장 짧은 경로의 이동거리만 밝히면 된다.
이 문제는 가장 짧은 경로를 ‘효율적으로’ 찾는 것이 목적이 아니다.
여러분은 모든 가능한 경로를 살펴서 해를 찾아도 좋다.
모든 경우를 체계적으로 따질 수 있으면 정답을 맞출 수 있다.
[제약사항]
고객의 수 N은 2≤N≤10 이다.
그리고 회사의 좌표, 집의 좌표를 포함한 모든 N+2개의 좌표는 서로 다른 위치에 있으며 좌표의 값은 0이상 100 이하의 정수로 이루어진다.
[입력]
가장 첫줄은 전체 테스트케이스의 수이다.
이후, 두 줄에 테스트 케이스 하나씩이 차례로 주어진다.
각 테스트 케이스의 첫째 줄에는 고객의 수 N이 주어진다. 둘째 줄에는 회사의 좌표,집의 좌표, N명의 고객의 좌표가 차례로 나열된다.
좌표는 (x,y)쌍으로 구성되는데 입력에서는 x와 y가 공백으로 구분되어 제공된다.
[출력]
총 10줄에 10개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음 최단 경로의 이동거리를 기록한다. 여기서 x는 테스트 케이스의 번호다.
입력
10
5
0 0 100 100 70 40 30 10 10 5 90 70 50 20
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
...
출력
#1 200
#2 304
#3 366
...
풀이
문제 유형 : TSP(Travelling Salesman Problem : 여행하는 외판원 문제)
-> 순열, 백트랙킹
1. 모든 집을 방문하는 순열을 구한다.
2. 현재까지의 이동경로를 더하면서 만약 이미 구한 정답보다 커지게 된다면 잘라낸다.(백트랙킹 가지치기)
3. N개의 집을 모두 돌았다면 마지막으로 집으로 가는 경로를 더해 최솟값을 찾아 출력한다.
코드
import java.io.*;
import java.util.*;
public class Solution_d5_1247_최적경로 {
static int N, ansCost;
static int[] comp, hous;
static int[][] cust;
static boolean[] isVisited;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
for(int tc=1; tc<=T; tc++) {
N = Integer.parseInt(br.readLine());
comp = new int[2];
hous = new int[2];
cust = new int[N][2];
st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<2; i++) {
comp[i] = Integer.parseInt(st.nextToken());
}
for(int i=0; i<2; i++) {
hous[i] = Integer.parseInt(st.nextToken());
}
for(int i=0; i<N; i++) {
for(int j=0; j<2; j++) {
cust[i][j] = Integer.parseInt(st.nextToken());
}
}
// : 입력 종료
ansCost = Integer.MAX_VALUE;
isVisited = new boolean[N];
perm(0, comp[0], comp[1], 0);
sb.append("#").append(tc).append(" ").append(ansCost).append("\n");
}
System.out.println(sb.toString());
br.close();
}
static void perm(int cnt, int prex, int prey, int total) {
if(cnt==N) {
total += Math.abs(prex-hous[0]) + Math.abs(prey - hous[1]);
ansCost = Math.min(ansCost, total);
return;
}
for(int i=0; i<N; i++) {
if(isVisited[i]) continue;
int tmp = total + Math.abs(prex-cust[i][0]) + Math.abs(prey-cust[i][1]);
if(tmp < ansCost) {
isVisited[i] = true;
perm(cnt+1, cust[i][0], cust[i][1], tmp);
isVisited[i] = false;
}
}
}
}
