[JAVA] 1247번 최적 경로

[JAVA] 1247번 최적 경로

문제

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

풀이

회사, 집, 고객의 위치를 모두 구한 다음, 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); } } }

from http://pekahblog.tistory.com/156 by ccl(S) rewrite - 2021-09-20 06:02:01