1247. [S/W 문제해결 응용] 3일차 - 최적 경로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD 

SW Expert Academy

 

문제 해석

N명의 고객에게 배달을 하려고 합니다.

회사, 집, 각 고객의 위치는 좌표(x, y)로 주어집니다.

두 위치사이의 거리는 | x1 - x2 | + | y1 - y2|로 계산됩니다.

 

N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 합니다.

 

회사를 출발해서 고객들에게 모두 방문하고 집으로 돌아가는 경로 중 이동거리가 가장 짧은 경로를 찾으세요.

 

문제 풀이 전 설계

그래프 탐색 문제 같습니다.

회사에서 시작해서 어느 고객에게 먼저 가는 것이 빠를 것인가를 계산해야 하는데 탐욕적으로 생각해서 가장 가까운 고객에게 접근한다면 안될 것 같다는 생각이 강하게 듭니다.

 

N의 범위가 2<= N <= 10이기 때문에 모든 경우의 수를 따져도 10! 이 소요되기 때문에 고객에게 갈 수 있는 경우를 모두 조합하여 최솟값을 찾는데 최솟값을 찾는도 중 현재 가지고 있는 최솟값보다 크다면 이동을 멈추는 가지치기 =  백 트레킹을 통해 해결할 수 있을 것 같습니다.

 

 

코드

package day0217;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Coord {
	int y;
	int x;

	public Coord(int x, int y) {		
		this.x = x;
		this.y = y;
	}

}

public class Solution_1247_최적경로 {

	static int distance;
	static int N;
	static Coord[] customerArray;
	static Coord home;
	static boolean[] visited;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= T; tc++) {
			distance = Integer.MAX_VALUE;
			N = Integer.parseInt(br.readLine());
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			// 회사
			Coord office = new Coord(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
			// 집
			home = new Coord(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
			// N명의 고객에 대한 좌표
			customerArray = new Coord[N];
			visited = new boolean[N];
			for (int i = 0; i < N; i++) {				
				customerArray[i] = new Coord(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
			}
			
			searchDistance(0, office, 0);
			
			sb.append("#"+tc + " " + distance + "\n");
		}
		System.out.println(sb);
	}

	// startCoord = 시작점
	private static void searchDistance(int cnt, Coord startCoord, int tempDistance) {
		
		//현재 가지고 있는 거리를 넘어버리계되면 계산할 필요 없음
		if(tempDistance >= distance) {
			return;
		}
		
		if(cnt == N) {
			//회사로부터 고객들을 순회하는것은 완료되었으나 마지막 고객과 회사와의 거리
			int tempValue = tempDistance + getDistance(startCoord, home);
			if(tempValue < distance) {
				distance = tempDistance + getDistance(startCoord, home);
			}
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(visited[i]) {
				continue;
			}
			visited[i] = true;
			searchDistance(cnt+1,customerArray[i],tempDistance+getDistance(startCoord,customerArray[i]));
			visited[i] = false;
		}
		
	}
	private static int getDistance(Coord startCoord, Coord destinationCoord) {
		
		return (Math.abs(startCoord.x - destinationCoord.x) + Math.abs(startCoord.y - destinationCoord.y));
	}
}