[백준] 15686번: 치킨 배달 - JAVA

🔗 문제 링크

BOJ 15686번: 치킨 배달

15686번: 치킨 배달

 

📝 풀이 과정

치킨 집을 M개만큼 선택하여 각 집과의 치킨거리의 합이 가장 작을 때를 구하는 문제이다.

 

switch를 활용해 입력 값이 1일 때는 집(home) List에 추가해주었고, 2일 때는 치킨집(chicken) List에 추가하여 위치들을 추가해 주었다.

switch (sc.nextInt()) {
    case 1:
        home.add(new int[]{i, j});
        break;
    case 2:
        chicken.add(new int[]{i, j});
        break;
}

 

1번, 2번 치킨집을 선택하는 경우와 2번, 1번 치킨집을 선택하는 경우는 같은 케이스이므로 combination을 활용하였다.

 

치킨집의 크기만큼 ck배열을 생성한 뒤, 재귀를 통해 선택한 idx값을 넘겨주며 idx의 다음 인덱스의 치킨집만을 선택하도록 하였고, 선택할 때마다 ck 배열에 true로 표시하고cnt값을 증가시켜주었다.

 

cnt의 값이 M과 같아지면 for문을 사용해 선택한 치킨집과 집과의 거리 중 최소값을 누적하여 ans 값을 갱신하였다.

 

💻 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int N, M, ans = Integer.MAX_VALUE;
    static boolean[] ck;
    static List<int[]> home, chicken;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        home = new ArrayList<>();
        chicken = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                switch (sc.nextInt()) {
                    case 1:
                        home.add(new int[]{i, j});
                        break;
                    case 2:
                        chicken.add(new int[]{i, j});
                        break;
                }
        }
        ck = new boolean[chicken.size()];
        comb(-1, 0);

        System.out.println(ans);
    }

    static void comb(int idx, int cnt) {
        if (cnt == M) {
            int dist = 0;

            for (int[] h : home) {
                int tmp = Integer.MAX_VALUE;
                for (int i = 0; i < ck.length; i++) {
                    if (ck[i])
                        tmp = Math.min(tmp, Math.abs(h[0] - chicken.get(i)[0]) + Math.abs(h[1] - chicken.get(i)[1]));
                }
                dist += tmp;
            }
            ans = Math.min(ans, dist);
            return;
        }

        for (int i = idx + 1; i < ck.length; i++) {
            ck[i] = true;
            comb(i, cnt + 1);
            ck[i] = false;
        }
    }
}

📊 제출 결과