[Algorithm] SWEA 1247 최적경로

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

SW Expert Academy

 

---

 

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

public class Solution_SWEA_1247_최적경로 {
	
	static int N;
	static Node company, house;
	static Node[] customers;
	static int min;
	
	static class Node {
		int x, y;
		public Node (int y, int x) {
			this.y = y;	this.x = x;
		}
	}
	
    
	private static void optimalPath(int n, int cnt, Node[] order, boolean[] visited, int distance) {
		if (distance > min)	return; // 백트래킹 가지치기
		
		if (cnt == n) {
			min = Math.min(min, distance + Math.abs(house.y-order[n-1].y) + Math.abs(house.x-order[n-1].x));
			return;
		}
		
		
		for (int i = 0; i < n; i++) {
			if(visited[i])	continue;
			
			visited[i] = true;
			order[cnt] = customers[i];
			if(cnt == 0)	optimalPath(n, cnt+1, order, visited, distance + Math.abs(company.y-order[cnt].y) + Math.abs(company.x-order[cnt].x));
			else	optimalPath(n, cnt+1, order, visited, distance + Math.abs(order[cnt-1].y-order[cnt].y) + Math.abs(order[cnt-1].x-order[cnt].x));
			visited[i] = false;
		}
	}

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		for(int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine()); // 고객의 수
			customers = new Node[N];
			
			st = new StringTokenizer(br.readLine());
			company = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));	// 회사의 좌표
			house = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); // 집의 좌표
			
			for(int n = 0; n < N; n++)	customers[n] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); // 고객의 좌표
			
			min = Integer.MAX_VALUE;
			optimalPath(N, 0, new Node[N], new boolean[N], 0);
			System.out.println("#" + t + " " + min);
		}
	}
}