[Algorithm] 치킨 배달

조합을 이용한 문제

자바에서 조합을 해결하는 방식 잘 이해할 것. 계속 공부해야함.

[Algorithm] JAVA에서 조합 (Combination)

import java.util.*;

class Combination {
    private int n; // 총 치킨 집 수
    private int r; // 선택하는 치킨 집 수
    private int[] now; // 현재 조합 (인덱스로 저장)
    private ArrayList<ArrayList<Position>> result; // 최종 조합

    public ArrayList<ArrayList<Position>> getResult() {
        return this.result;
    }

    public Combination (int n, int r) {
        this.n = n;
        this.r = r;
        this.now = new int[r];
        this.result = new ArrayList<ArrayList<Position>>();
    }

    public void comb(ArrayList<Position> arr, int depth, int index, int target) {
        if (depth == r) {
            // 다 고른 경우
            ArrayList<Position> tmp = new ArrayList<>();
            for (int i = 0; i < now.length; i++) {
                tmp.add(arr.get(now[i]));
            }
            result.add(tmp);
            return;
        }
        // 모두 확인한 경우
        if (target == n) return;
        now[index] = target;
        // 하나 선택하고 r-1개 찾는 경우
        comb(arr, depth+1, index+1, target+1);
        // 선택하지 않고 r개 찾는 경우
        comb(arr, depth, index, target+1);
    }

}

class Position {
    private int x;
    private int y;

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

    public int getX() {
        return this.x;
    }
    
    public int getY() {
        return this.y;
    }
}

class Main {

    public static int n, m;
    public static int[][] map = new int[51][51];
    public static ArrayList<Position> home = new ArrayList<>();
    public static ArrayList<Position> chicken = new ArrayList<>();

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 1) home.add(new Position(i, j));
                else if (map[i][j] == 2) chicken.add(new Position(i, j));
            }
        }
        sc.close();
        
        Combination com = new Combination(chicken.size(), m);
        com.comb(chicken, 0, 0, 0);
        ArrayList<ArrayList<Position>> chickenList = com.getResult();

        // chickenList에는 m개의 치킨집을 고른 경우의 수 리스트가 들어있다.
        // 각각의 리스트에서 치킨거리 계산.
        int result = (int) 1e9;
        for (int i = 0; i < chickenList.size(); i++) {
            ArrayList<Position> c = chickenList.get(i);
            int distance = 0;
            for (int j = 0; j < home.size(); j++) {
                int tmp = (int) 1e9;
                for (int k = 0; k < c.size(); k++) {
                    tmp = Math.min(Math.abs(home.get(j).getX() -c.get(k).getX())
                        + Math.abs(home.get(j).getY() - c.get(k).getY()), tmp);
                }
                distance += tmp;
            }
            result = Math.min(result, distance);
        }
        
        System.out.println(result);
    }
    
}

 

먼저, 치킨집 현재 갯수에서 m개만 고르는 경우의 수를 조합으로 정한다.

그 후에는 연산. 각 집마다 최소 치킨거리들의 합을 구한다. 그 합들을 비교해 최소값을 구한다.