[SW expert Academy] SWEA 1247번 최적 경로 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [SW expert Academy] SWEA 1247번 최적 경로 자바(Java)

1) 난이도 : D5

 

2) 문제번호 : 1247번

 

3) 문제 출처

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE&problemTitle=%EC%B5%9C%EC%A0%81&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

2. 문제

삼성전자의 서비스 기사인 김대리는 회사에서 출발하여 냉장고 배달을 위해 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명 사이의 고객 좌표가 주어질 때,

회사에서 출발해서 이들을 모두 방문하고 집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾는 프로그램을 작성하라.

여러분의 프로그램은 가장 짧은 경로의 이동거리만 밝히면 된다.

이 문제는 가장 짧은 경로를 ‘효율적으로’ 찾는 것이 목적이 아니다.

여러분은 모든 가능한 경로를 살펴서 해를 찾아도 좋다.

모든 경우를 체계적으로 따질 수 있으면 정답을 맞출 수 있다.

 

3. 제약사항

- 고객의 수 N은 2≤N≤10 이다.

- 그리고 회사의 좌표, 집의 좌표를 포함한 모든 N+2개의 좌표는 서로 다른 위치에 있으며 좌표의 값은 0이상 100 이하의 정수로 이루어진다.

 

4. 입력

가장 첫줄은 전체 테스트케이스의 수이다.

이후, 두 줄에 테스트 케이스 하나씩이 차례로 주어진다.

각 테스트 케이스의 첫째 줄에는 고객의 수 N이 주어진다. 둘째 줄에는 회사의 좌표,집의 좌표, N명의 고객의 좌표가 차례로 나열된다.

좌표는 (x,y)쌍으로 구성되는데 입력에서는 x와 y가 공백으로 구분되어 제공된다.

 

5. 출력

총 10줄에 10개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음 최단 경로의 이동거리를 기록한다. 여기서 x는 테스트 케이스의 번호다.

 

6. 풀이

- 순열을 생성해서 풀면 되는데, 만약 다 방문했다면 거리 계산 -> Math.abs()를 사용하여 계산

7. 소스 코드

import java.util.*;

public class Solution {
	static int N;
	static int Min;
	
	public static void Perm(int num,int[][] map, int[] result, boolean[] check) {
		//집도착
		if(num==N+1) {
			int sum = 0;
			//최소 거리의 합 계산
			for(int i=0;i<N+1;i++) {
				sum += Math.abs(map[result[i]][0]-map[result[i+1]][0]) + Math.abs(map[result[i]][1]-map[result[i+1]][1]);
			}
			
			//가지치기->실행시간 줄일 수 있음.
			if(sum<Min) Min = sum;
			return;
		}
		
		//집을 0과 방문으로 체크
		result[0] = 0;
		check[0] = true;
		
		//회사를 N+1과 방문으로 체크
		result[N+1] = N+1;
		check[N+1] = true;
		
		
		//순열 생성
		for(int i=1;i<N+1;i++) {
			if(check[i]) continue;
			result[num] = i;
			check[i] = true;
			Perm(num+1,map,result,check);
			check[i] = false;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();//테스트케이스 개수 입력
		
		for(int tc=1;tc<=T;tc++) {
			N = sc.nextInt();//고객의 수
			
			int[][] map = new int[N+2][2]; //좌표저장배열
			boolean[] check = new boolean[N+2]; //방문 체크
			int[] result = new int[N+2]; //뽑는 결과
			
			//최소
			Min = Integer.MAX_VALUE;
			
			//집좌표
			map[0][0] = sc.nextInt();
			map[0][1] = sc.nextInt();
			
			//회사좌표
			map[N+1][0] = sc.nextInt();
			map[N+1][1] = sc.nextInt();
			
			//고객의 좌표 입력 받아서 1~N까지 입력
			for(int i=1;i<=N;i++) {
				map[i][0] = sc.nextInt();
				map[i][1] = sc.nextInt();
			}
			Perm(1,map,result,check);
			System.out.printf("#%d %d\n",tc,Min);
		}
		
	}
	
	
}

---