[SWEA] 1247번: 최적 경로(Java)

💡 문제

문제

삼성전자의 서비스 기사인 김대리는 회사에서 출발하여 냉장고 배달을 위해 N명의 고객을 방문하고 자신의 집에 돌아가려한다.

회사와 집의 위치, 그리고 각 고객의 위치는 이차원 정수 좌표 (x, y)로 주어지고 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100)

두 위치 (x1, y1)와 (x2, y2) 사이의 거리는 |x1-x2| + |y1-y2|으로 계산된다.

여기서 |x|는 x의 절대값을 의미하며 |3| = |-3| = 3이다. 회사의 좌표, 집의 좌표, 고객들의 좌표는 모두 다르다.

회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장 짧은 것을 찾으려 한다.

회사와 집의 좌표가 주어지고, 2명에서 10명 사이의 고객 좌표가 주어질 때,

회사에서 출발해서 이들을

모두 방문하고

집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾는 프로그램을 작성하라.

여러분의 프로그램은 가장 짧은 경로의 이동거리만 밝히면 된다.

이 문제는 가장 짧은 경로를 ‘효율적으로’ 찾는 것이 목적이 아니다.

여러분은 모든 가능한 경로를 살펴서 해를 찾아도 좋다.

모든 경우를 체계적으로 따질 수 있으면 정답을 맞출 수 있다.

[제약사항]

고객의 수 N은 2≤N≤10 이다.

그리고 회사의 좌표, 집의 좌표를 포함한 모든 N+2개의 좌표는 서로 다른 위치에 있으며 좌표의 값은 0이상 100 이하의 정수로 이루어진다.

[입력]

가장 첫줄은 전체 테스트케이스의 수이다.

이후, 두 줄에 테스트 케이스 하나씩이 차례로 주어진다.

각 테스트 케이스의 첫째 줄에는 고객의 수 N이 주어진다. 둘째 줄에는 회사의 좌표,집의 좌표, N명의 고객의 좌표가 차례로 나열된다.

좌표는 (x,y)쌍으로 구성되는데 입력에서는 x와 y가 공백으로 구분되어 제공된다.

[출력]

총 10줄에 10개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음 최단 경로의 이동거리를 기록한다. 여기서 x는 테스트 케이스의 번호다.

예제 입력 1

10
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
...

예제 출력 1

#1 200
#2 304
#3 366
...

---

💡 접근 방법

---

🤦‍♀️ My Solution

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

public class SW_1247 {

    static int T, N, comY, comX, homeX, homeY, min;
    static int[][] cust; // 고객의 정보
    // 순열, 조합, 부분집합 -> 암기 수준으로 되어있어야함
    static int[] tgt;
    static boolean[] select;

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

        for (int t = 1; t < T; t++) {
            min = Integer.MAX_VALUE;

            N = Integer.parseInt(br.readLine());// 고객수
            cust = new int[N][2];
            select = new boolean[N];
            tgt = new int[N]; //

            StringTokenizer st = new StringTokenizer(br.readLine());
            comY = Integer.parseInt(st.nextToken());
            comX = Integer.parseInt(st.nextToken());

            homeY = Integer.parseInt(st.nextToken());
            homeX = Integer.parseInt(st.nextToken());

            // N개 고객에 대한 정보
            for (int i = 0; i < N; i++) { // y:0 x:1
                cust[i][0] = Integer.parseInt(st.nextToken()); // y좌표
                cust[i][1] = Integer.parseInt(st.nextToken()); // x좌표

            }

            // 순열
            perm(0); // 0:tat의 맨 앞부터 채우겠다
            System.out.println("#" + t + " " + min);
        }
    }

    static void perm(int tgtIdx) {
        // 기저조건
        if (tgtIdx == N) {
            // compete code
            // 현재 순열의 경우의 수가 하나 완성된 상태
            // 거리계산 후 최솟값인지 확인, 갱신

            // 회사 -> 첫 번째 고객
            int sum = distance(comY, comX, cust[tgt[0]][0], cust[tgt[0]][1]);

            // 첫 번째 고객 -> 마지막 고객
            for (int i = 0; i < N - 1; i++) {
                sum += distance(cust[tgt[i]][0], cust[tgt[i]][1], cust[tgt[i + 1]][0], cust[tgt[i + 1]][1]);
            }

            // 마지막 고객 -> 집
            sum += distance(cust[tgt[N - 1]][0], cust[tgt[N - 1]][1], homeY, homeX);

            min = Math.min(min, sum);
            return;
        }

        // src(cust)의 N개의 고객 중 하나씩 선택해 가는 과정을 거친다
        // 단 이미 이전에 선택한 고객은 제외함
        for (int i = 0; i < N; i++) {
            if (select[i])
                continue; // 이미 선택된 고객이면 스킵
            select[i] = true;
            tgt[tgtIdx] = i;// 현재 tgrIdx자리에 i를 선택했으니 다음 자리를 보러간다
            perm(tgtIdx + 1);
            select[i] = false; // 다시 되돌려준다
        }
    }

    static int distance(int y1, int x1, int y2, int x2) {
        return Math.abs(y1 - y2) + Math.abs(x1 - x2);

    }

}

---