백준 15686 : 치킨 배달 [JAVA]

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

1. 문제 설명

2. 문제 풀이

구현 해야 할 것

•  N X N 크기의 리스트를 받아 집, 치킨가게의 위치를 각각의 리스트에 받는다.
• M개의 치킨집을 골라야 하므로 조합을 이용하여 visited 배열을 만들어 M개의 자리에 true 값을 넣는다.
• 조합이 완성이 되면 각각의 집에서 고른 치킨집중에서 가장 가까운 거리를 총 거리에 더해준다
• 완성된 총 거리들중 가장 가까운 거리를 구한다.

 

3. 코드

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

public class Main {

    static int n, m, cnt;
    static int arr[][];
    static ArrayList<int []> chicken, home;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][n];
        home = new ArrayList<>();
        chicken = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1) {
                    home.add(new int[]{i, j});
                } else if (arr[i][j] == 2) {
                    chicken.add(new int[]{i, j});
                }
            }
        }
        ArrayList<int []> c = new ArrayList<>();
        cnt = (int) 1e9;
        combination(0, c);
        System.out.println(cnt);
    }

    static void combination(int idx, ArrayList<int []> choice) {
        if (choice.size() == m) {
            cnt = Math.min(cal(choice), cnt);
            return;
        }
        for (int i = idx; i < chicken.size(); i++) {
            choice.add(chicken.get(i));
            combination(i + 1, choice);
            choice.remove(choice.size()-1);
        }
    }

    static int cal(ArrayList<int []> choice) {
        int res = 0;
        for (int i = 0; i < home.size(); i++) {
            int distance = (int) 1e9;
            for (int j = 0; j < choice.size(); j++) {
                distance = Math.min(distance, Math.abs(choice.get(j)[0] - home.get(i)[0]) + Math.abs(choice.get(j)[1] - home.get(i)[1]));
            }
            res += distance;
        }
        return res;
    }
}