[알고리즘] 1247. 최적경로

0. 문제

 

SW Expert Academy

 

---

1. 문제 이해

 

1. 백트래킹
2. 순열
3. DP

 

---

2. 제출

 

가. 순열

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class SWEA1247 {

    static int n, ret;
    static boolean[] vis;
    static Point work, home;
    static Point[] custs;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();

        int T = Integer.parseInt(st.nextToken());

        for(int tc=1; tc<=T; tc++) {
            //초기화
            ret = Integer.MAX_VALUE;
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            custs = new Point[n];
            vis= new boolean[n];

            // 좌표 저장
            st = new StringTokenizer(br.readLine());
            work = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            home = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            for(int i=0; i<n; i++) {
                custs[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }
            // 정렬 - 최대한 빠른 횟수 안에 최소값을 찾기 위해서
            Arrays.sort(custs);

            solve(0, 0, work);

            sb.append("#").append(tc).append(" ").append(ret).append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    // 순열
    private static void solve(int depth, int sum, Point cur) {
        // 가지치기
        if(sum > ret) return;

        // 기저조건
        if(depth==n) {
            // sum에 집까지 거리 더하기
            sum += Math.abs(cur.y - home.y) + Math.abs(cur.x - home.x);
            ret = Math.min(ret, sum);
            return;
        }

        for(int i=0; i<n; i++) {
            if(cur == custs[i]) continue;
            if(vis[i]) continue;

            vis[i]=true;
            int dis = Math.abs(cur.y - custs[i].y) + Math.abs(cur.x - custs[i].x);
            solve(depth+1, sum+dis, custs[i]);
            vis[i]=false;
        }
    }

    private static class Point implements Comparable<Point> {
        int y;
        int x;
        Point(int y, int x){
            this.y = y;
            this.x = x;
        }

        @Override
        public int compareTo(Point o) {
            return (this.y==o.y) ? this.x - o.x : this.y - o.x;
        }

        @Override
        public String toString() {
            return "Home [y=" + y + ", x=" + x + "]";
        }

    }

}

가능한 순열을 직접 생성하여 최솟값을 찾는다.

 

---

나. DP

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// DP로 풀어보기
public class SWEA1247_2 {

    static int n, ret;
    static Point work, home;
    static Point[] points;
    static int[][] dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuffer sb= new StringBuffer();

        int T = Integer.parseInt(st.nextToken());
        for(int tc=1; tc<=T; tc++) {
            //초기화
            ret = Integer.MAX_VALUE;
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            points = new Point[++n]; // 직장 + 고객

            //dp 초기화
            dp = new int[n][(1<<n)-1]; // y : 가장 최근에 방문한 고객, x : 방문한 모든 고객
            for(int i=0; i<n; i++) Arrays.fill(dp[i], -1); // 가본적 없음을 표시

            // 좌표 저장
            st = new StringTokenizer(br.readLine());
            work = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            home = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            for(int i=1; i<n; i++) {
                points[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }            
            points[0]=work;

            // 직장 -> 고객 -> 집 최소 비용
            ret = solve(0, 1);

            sb.append("#").append(tc).append(" ").append(ret).append("\n");
        }
        System.out.println(sb);
        br.close();
    }

    // now -> vis 하지 않은 도시들 -> 집 최소 거리 반환.
    private static int solve(int now, int vis){
        if(vis == (1<<n)-1) { // 모든 고객 방문 후 집까지 가는 비용
            return getDistance(points[now], home);
        }
        // 이미 계산했으면 값을 재사용.
        if(dp[now][vis] != -1) return dp[now][vis];

        // 처음이자 마지막으로 계산
        dp[now][vis] = Integer.MAX_VALUE; // 초기화
        for(int next=0; next<n; next++){
            if((vis & (1<<next)) != 0) continue; // 가본적 있으면 패스
            int newDistance = solve(next, vis | (1<<next)) + getDistance(points[now], points[next]);
            dp[now][vis] = Math.min(dp[now][vis], newDistance);
        }

        // 새로 계산한 값 반환
        return dp[now][vis];
    }

    private static int getDistance(Point from, Point to){
        return Math.abs(from.y - to.y)+Math.abs(from.x - to.x);
    }

    private static class Point {
        int y;
        int x;
        Point(int y, int x){
            this.y = y;
            this.x = x;
        }

        @Override
        public String toString() {
            return "Home [y=" + y + ", x=" + x + "]";
        }

    }    

}

순열을 DP로 푸는 방법이다.

 

---