[JAVA] 1247번 최적 경로

문제

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

SW Expert Academy

 

풀이

회사, 집, 고객의 위치를 모두 구한 다음, dfs를 돌며 가까운 고객의 위치를 계속해서 확인해보며 답을 찾을 수 있었다.

 

import java.awt.Point;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SWEA1247_최적경로 {
	static int N;
	static Point[] customer;
	static Point company;
	static Point home;
	static boolean visited[];
	static int result;
	
	public static int getDistance(int x, int y, int cx, int cy) {
		return Math.abs(x-cx) + Math.abs(y-cy);
	}
	
	public static void dfs(int cur, int x, int y, int count) {
		if (cur == N) {
			count += getDistance(x, y, company.x, company.y);
			result = Math.min(result, count);
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				dfs(cur + 1, customer[i].x, customer[i].y , count + getDistance(x, y, customer[i].x, customer[i].y));
				visited[i] = false;
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input1247.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			customer = new Point[N];
			visited = new boolean[N];
			result = Integer.MAX_VALUE;
			
			st = new StringTokenizer(br.readLine());
			company = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			home = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			
			int k = 0;
			for (int i = 4; i < 4+N; i++) {
				customer[k++] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			
			dfs(0, home.x, home.y, 0);
			
			System.out.println("#" + tc + " " + result);
		}
	}
}