[SWEA/D5] SWEA 1247 [S/W 문제해결 응용] 3일차 - 최적 경로(Java)

문제 출처

SW Expert Academy

 

알고리즘 분류

• 백트래킹

 

풀이

회사에서 시작해서 최대 10명의 손님을 방문한 후 집으로 도착하는 경우의 수는 10! = 3,628,800가지이다.

백트래킹을 사용해서 최대 10명의 손님을 방문하는 모든 경우의 수를 탐색하며 이동하는 거리를 계산한다.

모든 손님을 방문했다면 마지막 손님의 위치와 집의 위치 사이의 거리까지 더한 값이 회사에서 출발하여 모든 고객에게 냉장고를 방문하고 집에 도착했을 때 걸린 이동 거리가 된다.

이 이동 거리의 최솟값을 구한다.

 

코드

import java.io.*;
import java.util.*;

public class Solution {
	
	static boolean[] Visited = new boolean[11];
	static int Answer;
	
	public static class PositionInfo {
		int Y, X;
		
		public PositionInfo(int Y, int X) {
			this.Y = Y;
			this.X = X;
		}
	}
	
	public static void init() {
		for (int i = 0; i < 11; i++) {
			Visited[i] = false;
		}
		Answer = 1000000000;
	}
	
	public static void dfs(int N, int Depth, int Sum, ArrayList<PositionInfo> customers, PositionInfo Now, PositionInfo home) {
		if (Depth == N) {
			Sum += Math.abs(Now.Y - home.Y) + Math.abs(Now.X - home.X);
			Answer = Math.min(Answer, Sum);
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (!Visited[i]) {
				Visited[i] = true;
				PositionInfo Next = customers.get(i);
				dfs(N, Depth + 1, Sum + Math.abs(Now.Y - Next.Y) + Math.abs(Now.X - Next.X), customers, Next, home);
				Visited[i] = false; 
			}
		}
	}
	
	public static void settings(int N, PositionInfo company, PositionInfo home, ArrayList<PositionInfo> customers) {
		dfs(N, 0, 0, customers, company, home);
	}
	
	public static void find_Answer(int Case) {
		System.out.println("#" + Case + " " + Answer);
	}
	
	public static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for (int i = 1; i <= T; i++) {
			init();
			String[] input = br.readLine().split(" ");
			int N = Integer.parseInt(input[0]);
			
			input = br.readLine().split(" ");
			int A = Integer.parseInt(input[0]);
			int B = Integer.parseInt(input[1]);
			int C = Integer.parseInt(input[2]);
			int D = Integer.parseInt(input[3]);
			
			PositionInfo company = new PositionInfo(A, B);
			PositionInfo home = new PositionInfo(C, D);
			ArrayList<PositionInfo> customers = new ArrayList<PositionInfo>();
			for (int j = 0; j < (N * 2); j += 2) {
				int Y = Integer.parseInt(input[j + 4]);
				int X = Integer.parseInt(input[j + 5]);
				customers.add(new PositionInfo(Y, X));
			}
			
			settings(N, company, home, customers);
			find_Answer(i);
		}
	}

	public static void main(String[] args) throws IOException {
		input();
	}

}