[조합(재귀), 완전탐색] 치킨배달

[삼성 SW 역량 테스트 기출 문제] 치킨배달

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

package com.company;

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

public class Chicken {

    static List<Location> shops = new ArrayList<>(); //치킨집의 위치를 담고있는 리스트
    static List<Location> homes = new ArrayList<>(); //집의 위치를 담고있는 리스트
    static int minDisSum = 10000; //모든 집에서의 치킨거리 합 중에서 최솟값

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int pick = sc.nextInt();
        int[][] map = new int[N+1][N+1];

        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                map[i][j] = sc.nextInt();

                //집과 치킨집의 위치를 얻음
                if(map[i][j]==1){
                    Location loc = new Location(i,j);
                    homes.add(loc);
                }else if(map[i][j]==2){
                    Location loc = new Location(i,j);
                    shops.add(loc);
                }
            }//for-j
        }//for-i

        int[] arr = new int[ pick ];
        combination(arr, 0, shops.size(), pick, 0);

        System.out.println(minDisSum);

    }


    //조합의 순서쌍을 구함
    static void combination(int[] arr, int index, int n, int r, int target){

        if(r==0){
            chicken(arr);
        }else if(target==n){
            return;
        }else{
            arr[index] = target;
            combination(arr, index+1, n, r-1, target+1);
            combination(arr, index, n, r, target+1);
        }
    }

    //하나의 경우에 대한 치킨거리
    static void chicken(int[] arr){

        //임의로 M개 골라진 치킨집 좌표 쌍
        List<Location> pickedShops = new ArrayList<>();
        for(int i=0; i<arr.length; i++){
            pickedShops.add( shops.get( arr[i] ) );
        }

        int disSum=0; //모든 집의 치킨거리 합

        for(int i=0; i<homes.size(); i++){ //집

            int homeToShopDis=10000; //각 집의 치킨거리
            for(int j=0; j<pickedShops.size(); j++){ //치킨집
                int distance = getDistance(homes.get(i), pickedShops.get(j));
                homeToShopDis = Math.min(homeToShopDis, distance);
            }
            disSum += homeToShopDis;
        }
        minDisSum = Math.min(disSum, minDisSum);
    }

    //두 좌표의 거리
    static int getDistance(Location loc1, Location loc2){
        return Math.abs(loc1.x-loc2.x) + Math.abs(loc1.y-loc2.y);
    }


    static class Location{
        int y;
        int x;
        Location(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
}

combination 설명: http://sunpil.tistory.com/50?category=748943

집에가서 교촌치킨 시켜먹어야지