[코딩테스트] SWEA 1247 최적경로(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 1247 최적경로입니다.

포인트

집과 회사의 위치는 고정되어 있고, 중간에 방문해야 하는 고객들의 위치를 어떤 순서로 방문할지 결정하는 것이 핵심 문제입니다.
경로는 다음과 같은 형태로 구성됩니다:

회사 → 고객 1 → 고객 2 → ... → 고객 n → 집

이때, n명의 고객을 어떤 순서로 방문할지 결정하여 전체 경로의 맨해튼 거리 합이 최소가 되도록 해야 합니다.
고객들의 방문 순서를 정하는 모든 경우를 탐색하려면 순열을 고려해야 하며, 이는 시간복잡도 O(n!)의 완전탐색 문제로 볼 수 있습니다.

최악의 경우 n = 10일 때, 총 경우의 수는 10! = 3,628,800이며, 이는 Java 기준으로 일반적인 환경에서 20초 이내에 충분히 처리 가능한 수준입니다.
따라서, n이 10 이하라면 완전탐색 방식으로도 무리가 없습니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Q1247 {
    static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static int testCase, N, ans = Integer.MAX_VALUE;
    private static Pair company, house;
    private static Pair[] customers;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        testCase = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 1; t <= testCase; t++) {
            N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            ans = Integer.MAX_VALUE;
            customers = new Pair[N];
            visited = new boolean[N];

            for (int i = 0; i < N + 2; i++) {
                if (i == 0) {
                    company = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                } else if (i == 1) {
                    house = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                } else {
                    customers[i - 2] = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                }
            }

            dfs(new ArrayList<Integer>(), 0);

            sb.append("#").append(t).append(" ").append(ans);
            if (t != testCase) {
                sb.append("\n");
            }
        }
        System.out.println(sb);
    }

    private static void dfs(List<Integer> orders, int cnt) {
        if (cnt == N) {
            int sum = 0;
            sum = getSum(orders, sum);
            ans = Math.min(ans, sum);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            orders.add(i);

            dfs(orders, cnt + 1);

            orders.remove(orders.size() - 1);
            visited[i] = false;
        }
    }

    private static int getSum(List<Integer> orders, int sum) {
        Pair cur = company;

        for (int nextIdx : orders) {
            Pair next = customers[nextIdx];
            sum += cal(cur, next);
            cur = next;
        }

        sum += Math.abs(cur.x - house.x) + Math.abs(cur.y - house.y);
        return sum;
    }

    private static int cal(Pair cur, Pair next) {
        return Math.abs(cur.x - next.x) + Math.abs(cur.y - next.y);
    }
}

/**
3
5
0 0 100 100 70 40 30 10 10 5 90 70 50 20
6
88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
10
39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36
*/

코드 설명

• 집, 회사, 고객을 Pair 클래스로 초기화합니다.
• dfs(List<Integer> orders, int cnt)
  고객의 방문 순서 = orders, cnt = 현재까지 고려한 고객의 수
  • 고객을 방문할 때마다 orders에 추가하고, visited 배열로 방문 여부 체크합니다.
  • 이후 dfs(orders, cnt+1)로 재귀 호출을 진행합니다.
  • 고객 수 cnt == n이면, 현재 순서대로 이동 거리 총합을 계산합니다