[SWEA 1247] 최적 경로 자바 DFS

문제

SWEA 1247 최적 경로 문제 자바 사용하여 DFS로 풀었음. 

SW Expert Academy

 

접근방식

배송지를 방문할 때마다 거리 계산을 해주고 최종 거리에 도착했을 때 최솟값을 찾아주면 된다. 

사실 거리 계산도 그렇고 DFS로 풀다보니 로직도 복잡할 건 없는데 시간을 줄이고 싶어서 min값보다 계산한 거리값이 큰 경우일 때는 리턴해주도록 짰다. 

public static void deliver(Point p,int count,int distance){
        if(distance >= min) return;
        if(n==count){
            distance += calDist(end,p);
            min = Math.min(min,distance);
        }else{
            for (int i=0;i<n;i++){
                if(!check[i]){
                    check[i] = true;
                    deliver(house[i],count+1,distance+calDist(p,house[i]));
                    check[i] = false;
                }
            }
        }
    }

풀이

import java.io.IOException;
import java.util.*;
 
class Point {
    int x,y;
 
    public Point(int x,int y){
        this.x = x;
        this.y = y;
    }
}
public class Solution {
    public static int n,min;
    public static Point start,end;
    public static Point[] house;
    public static boolean[] check;
    public static int calDist(Point a,Point b){
        return Math.abs(a.x-b.x)+Math.abs(a.y-b.y);
    }
 
    public static void deliver(Point p,int count,int distance){
        if(distance >= min) return;
        if(n==count){
            distance += calDist(end,p);
            min = Math.min(min,distance);
        }else{
            for (int i=0;i<n;i++){
                if(!check[i]){
                    check[i] = true;
                    deliver(house[i],count+1,distance+calDist(p,house[i]));
                    check[i] = false;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        StringBuilder sb = new StringBuilder();
 
        for(int t=1;t<=T;t++){
            n = scanner.nextInt();
            start = new Point(scanner.nextInt(),scanner.nextInt());
            end = new Point(scanner.nextInt(),scanner.nextInt());
            house = new Point[n];
            check = new boolean[n];
            min = Integer.MAX_VALUE;
 
            for(int i=0;i<n;i++){
                house[i] = new Point(scanner.nextInt(),scanner.nextInt());
            }
 
            deliver(start,0,0);
 
            sb.append("#"+t+" "+min+"\n");
        }
        System.out.println(sb);
    }
}