[BOJ] 15686. 치킨 배달

이 문제는 조합을 사용하여 간단히 풀수있는 문제이다.

(전체치킨집수)C(제한된치킨집수) 와 같은 조합식을 세우고 이대로 접근하여 풀고 그 상황에서의 치킨거리의 최솟값을 구하면 쉽게 풀 수 있는 문제이다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_bj_15686_치킨배달 {
    
    
    static List<Pos> chicken;
    static List<Pos> home;
    
    static boolean[] visit;
    static Pos[] result;
    
    static int N,R;
    static int answer;
    
    static class Pos{
        int i,j;
        Pos(int i,int j){
            this.i=i;this.j=j;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));    
        StringTokenizer st = null;
        
        st=new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        R=Integer.parseInt(st.nextToken());
        
        chicken=new ArrayList<>();
        home=new ArrayList<>();
        
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                int num=Integer.parseInt(st.nextToken());
                if(num==1)    home.add(new Pos(i, j));
                else if(num==2) chicken.add(new Pos(i, j));
            }
        }
        
        
        result=new Pos[R];
        visit=new boolean[chicken.size()];
        
        answer=Integer.MAX_VALUE;
        comb(0,0);
        System.out.println(answer);
        
    }
    
    static void comb(int start,int depth) {
        if(depth==R) {
            func();
            return;
        }
        
        for(int i=start;i<chicken.size();i++) {
            if(visit[i]==false) {
                visit[i]=true;
                result[depth]=chicken.get(i);
                comb(i,depth+1);
                visit[i]=false;
            }
        }
    }
    
    static void func() {
        int sum=0;
        for(Pos ho : home) {    //집기준 치킨집 찾기
            int dis=Integer.MAX_VALUE;
            for(int i=0;i<R;i++) {
                Pos chi=result[i];
                
                dis=Math.min(dis,distance(chi.i, chi.j, ho.i, ho.j));
            }
            sum+=dis;
        }
        answer=Math.min(answer, sum);
    }
    
    static int distance(int row1,int col1, int row2, int col2) {
        return Math.abs(row1-row2) + Math.abs(col1-col2);
    }
}