문제
삼성전자의 서비스 기사인 김대리는 회사에서 출발하여 냉장고 배달을 위해 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는 테스트 케이스의 번호다.
일단 생각하기!
- 가장 짧은 경로를 효율적으로 찾는 것이 아니므로 n명의 고객 집을 순열을 이용하여 모든 순서의 경우의 수를 저장한 뒤, 가장 짧은 경로를 찾았다.
static배열인arr와isSelected그리고sum변수를 어디에 선언하느냐에 따라 답이 다르게 나와 여기서 한시간은 걸렸던 것 같다 ㅜㅜ 변수 선언 위치 잘 확인하기!
풀이
package SWEA;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
*
* @author 김유나
* 2023-08-17
*
* [문제] SWEA 1247번 최적 경로
* - 김대리의 회사와 집, 그리고 N명의 고객 집 좌표를 입력 받고 가장 짧은 경로의 이동거리를 구하라.
* - 이때, 경로는 |x1-x2| + |y1-y2|로 계산되며 효율적으로 찾지 않아도 된다.
* [아이디어]
* - 가장 짧은 경로를 "효율적으로" 찾지 않아도 된다고 했으니 n명의 고객 집을 순열을 이용하여 나열한 뒤, 가장 짧은 경로를 찾았다.
* - static 배열과 변수를 어디에 선언하느냐에 따라 답이 다르게 나와 생각보다 헤맸다.
*
* 메모리 : 21,252kb 실행 시간 : 2,172ms
*
*/
public class D5_1247_최적경로_김유나 {
static int[][] arr;
static int n, minPath, sum, startX, startY, endX, endY;
static boolean[] isSelected;
static int[] order;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int tc = Integer.parseInt(br.readLine()); // 테스트 케이스
for (int t = 1; t <= tc; t++) {
n = Integer.parseInt(br.readLine()); // 고객의 수
arr = new int[n][2]; // n x 2의 고객 집 좌표 (x, y)
isSelected = new boolean[n]; // 순열에 사용할 배열 : 선택되었는지 확인
order = new int[n]; // 선택된 인덱스 담을 배열
minPath = Integer.MAX_VALUE; // 가장 짧은 경로
st = new StringTokenizer(br.readLine());
startX = Integer.parseInt(st.nextToken()); // 회사 x좌표
startY = Integer.parseInt(st.nextToken()); // 회사 y좌표
endX = Integer.parseInt(st.nextToken()); // 집 x좌표
endY = Integer.parseInt(st.nextToken()); // 집 y좌표
for (int i = 0; i < n; i++) {
arr[i][0] = Integer.parseInt(st.nextToken()); // 고객 x좌표
arr[i][1] = Integer.parseInt(st.nextToken()); // 고객 y좌표
}
optimalPath(0);
System.out.println("#" + t + " " + minPath);
}
}
static void optimalPath(int count) {
sum = 0; // 이동거리 합
// n명의 순서를 모두 정했을 때
if (count == n) {
// 회사에서 첫번째 고객 집 이동거리
sum += Math.abs(startX - arr[order[0]][0]) + Math.abs(startY - arr[order[0]][1]);
// 마지막 고객 집에서 김대리 집 이동거리
sum += Math.abs(endX - arr[order[n - 1]][0]) + Math.abs(endY - arr[order[n - 1]][1]);
// 나머지 고객 집간의 이동거리
for (int i = 0; i < n - 1; i++) {
sum += Math.abs(arr[order[i]][0] - arr[order[i + 1]][0]) + Math.abs(arr[order[i]][1] - arr[order[i + 1]][1]);
}
minPath = Math.min(sum, minPath); // 가장 짧은 이동거리
return;
}
else {
for (int i = 0; i < n; i++) {
if (isSelected[i]) continue; // 이미 선택되었으면 continue
order[count] = i; // 아직 안 쓰였다면 i 대입
isSelected[i] = true; // 쓰였다고 체크 후
optimalPath(count + 1); // 재귀함수 호출 : count + 1을 넣어 다음 수 탐색
isSelected[i] = false; // 체크 해제
}
}
}
}
