[SWEA] 1247.최적 경로(순열).java

#. Problem

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

* The copyright in this matter is in SWEA

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

회사에서 출발해서 고객의 집을 모두 방문하고,

집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾아야 한다.

일단, 어느 집을 먼저 갈지 순서를 정해주어야 하는데

N개의 집들 중 N개를 나열해야하는 순열을 이용해야 한다.

nPn = n! 인데,

다행이 문제는 최대 N이 10이므로 10! = 3628800,

1초 안에 연산이 충분하다.

#. Code

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int T, N, res;
    static Point houses[], Office, home;
    static boolean visited[];
    static int sel[];
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            
            N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            houses = new Point[N];
            visited = new boolean[N];
            sel = new int[N];
            
            Office = 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++) 
                houses[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            
            res = 987654321;
            process(0, 0);
            
            System.out.println("#" + tc + " " + res);
        }
    }
    
    public static void process(int cnt, int idx) {
        // 순열이 완성되었다면 거리 계산
        if(cnt == N) {
            int sum = 0;
            // 집에서 첫 번째 고객 집까지의 거리
            sum += Math.abs(Office.x - houses[sel[0]].x) + Math.abs(Office.y - houses[sel[0]].y);
            // 이후 고객들이 집 방문
            for (int i = 1; i < N; i++) 
                sum += Math.abs(houses[sel[i]].x - houses[sel[i-1]].x) + Math.abs(houses[sel[i]].y - houses[sel[i-1]].y);
            // 마지막 들린 고객 집에서 내 집까지의 거리
            sum += Math.abs(home.x - houses[sel[N-1]].x) + Math.abs(home.y - houses[sel[N-1]].y);
            
            res = Math.min(res, sum);
        }
        
        // 순열 구하기
        for (int i = 0; i < N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                sel[idx] = i;
                process(cnt + 1, idx + 1);
                visited[i] = false;
            }
        }
    }
 
}

#. Code_v2

현재까지 거리를 파라미터로 넘겨주면서,

현재까지의 거리가 이미 구해진 경로보다 크면 가지치기를 해주었더니

약 2,500 ms 나 빠르게 해결할 수 있었다..

역시 재귀함수는 가지치기가 중요하다...

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution1247 {
 
    static int T, N, res;
    static Point customers[], Office, home;
    static boolean visited[];
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            
            N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            customers = new Point[N];
            visited = new boolean[N];
            
            Office = 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++) 
                customers[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            
            res = 987654321;
            process(0, Office, 0);
            
            System.out.println("#" + tc + " " + res);
        }
    }
    
    public static void process(int cnt, Point prev, int dist) {
        // 지금까지의 거리가 이미 구해진 경로보다 크면 더이상 확인할 필요가 없음
        if(dist >= res) return;
        // 순열이 완성되었다면 거리 계산
        if(cnt == N) {
            // 마지막 들린 고객 집에서 내 집까지의 거리
            dist += Math.abs(prev.x - home.x) + Math.abs(prev.y - home.y);
            res = Math.min(res, dist);
        }
        
        // 순열 구하기
        for (int i = 0; i < N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                process(cnt + 1, customers[i], dist + Math.abs(prev.x - customers[i].x) + Math.abs(prev.y - customers[i].y));
                visited[i] = false;
            }
        }
    }
 
}