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

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

SW Expert Academy

 

위 링크로 문제설명은 간략하게 한다.

회사 => 고객들의 좌표 => 집 

해당 루트에서 가장 최단거리를 출력하면 되며 거리는  |x1-x2| + |y1-y2| 로 계산된다.

나는 DFS 를 사용했으며 중복되지 않는 순열 인덱스 정보를 뽑아내어  고객좌표를 누적했다. 문제에서는 아래와 같이 효율성을 고려하지 않아도 된다고해서  그냥 DFS로 풀었는데 효율적으로 풀기위해 외판원 알고리즘(TSP) 로 다시 풀어보는게 좋을거 같다.

이 문제는 가장 짧은 경로를 ‘효율적으로’ 찾는 것이 목적이 아니다.여러분은 모든 가능한 경로를 살펴서 해를 찾아도 좋다

 

import java.util.*;
//좌표 클래스
class point{
    int y;
    int x;
    public point(int y, int x){
        this.y=y;
        this.x=x;
    }
}

public class Main {
    static int answer=0,dis=Integer.MAX_VALUE;
    static int n;
    static int[] pm;
    static int[] ch;
    static point current;
    static point company;
    static point home;
    static ArrayList<point> list;

    public void dfs(int l){
        // 고객들의 중복되지 않는 순열 인덱스로 접근
        if(l==n){
            int tmpDis=0;
            //항상 현재 위치를 먼저 회사로 지정
            current = company;
            for(int i=0;i<n;i++){
                point tmp = list.get(pm[i]);
                tmpDis+= Math.abs(current.y-tmp.y) + Math.abs(current.x- tmp.x);
                current = tmp;
            }
            tmpDis+=  Math.abs(current.y-home.y) + Math.abs(current.x- home.x);
            dis=Math.min(dis,tmpDis);
        }
        else{
            for(int i=0; i<n; i++){
                if(ch[i]==0){
                    ch[i]=1;
                    pm[l]=i;
                    dfs(l+1);
                    ch[i]=0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Main M = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        //회사
        int cy = sc.nextInt();
        int cx = sc.nextInt();
        company = new point(cy,cx);
        //집
        int hy = sc.nextInt();
        int hx = sc.nextInt();
        home =  new point(hy,hx);
        list = new ArrayList<>();
        for(int i=0;i<n;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            list.add(new point(a,b));
        }
        //dfs에서 중복되지 않는 순열을 뽑아내기 위한 pm배열과 접근제어하는 ch배열
        pm= new int[n];
        ch= new int[n];
        M.dfs(0);
        answer+=dis;
        System.out.println(answer);


    }
}