View

λ°˜μ‘ν˜•

문제

μ‚Όμ„±μ „μžμ˜ μ„œλΉ„μŠ€ 기사인 κΉ€λŒ€λ¦¬λŠ” νšŒμ‚¬μ—μ„œ μΆœλ°œν•˜μ—¬ 냉μž₯κ³  배달을 μœ„ν•΄ 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);

    }

}

λ°˜μ‘ν˜•
Share Link
reply
λ°˜μ‘ν˜•
Β«   2024/11   Β»
일 μ›” ν™” 수 λͺ© 금 ν† 
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30