치킨배달-15686번(java)

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

15686번: 치킨 배달

package a0813;

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

public class Main_bj_15686_치킨배달_서울_12반_이서영 {
	static int n,m;
	static StringTokenizer st;
	static int[][] arr;
	static ArrayList<Pair>chicken = new ArrayList<>();
	static ArrayList<Pair>house = new ArrayList<>();
	static int min = Integer.MAX_VALUE;
	
	static class Pair{
		int x, y;
		Pair(int x,int y){
			this.x =x;
			this.y = y;
		}
	}
	
	
	
	public static int findDistance(Pair[]chlist) {

			int total =0;
			for(int i=0; i<house.size(); i++) {
				
				Pair p = house.get(i);
				int hx = p.x;
				int hy = p.y;
				int hcmin = Integer.MAX_VALUE;
			
				for(int j=0; j<m; j++) {
					Pair q = chlist[j];
					int cx = q.x;
					int cy = q.y;
					int dist = Math.abs(hx-cx)+Math.abs(hy-cy);
					if(hcmin>dist) {hcmin = dist;}
				}
				total+=hcmin;
			}
			
		//	System.out.println(total);
			 
			return total;
		
		
	}
	
	
	// 조합으로 치킨집 m개를 고른다. 
	public static void pickChickenHouse( int idx,int cnt, Pair[]chlist, boolean[] chk) {
		
		if(cnt>m) {return;}
		
		if(cnt ==m) {
			int total = findDistance(chlist);
			if(total<min) {
				min = total;
			}
			return;
		}
		
        
		for(int i= idx; i<chicken.size(); i++) {
			if(chk[i]==false) {
			
				chk[i]=true;
				chlist[cnt]=chicken.get(i);
				
				pickChickenHouse(i+1,cnt+1,chlist,chk); //idx+1이아니라 i+1!!!
				
				chk[i]=false;
				chlist[cnt]=null;
			}
		}
		
		
	}
	
	
	
	public static void main(String[]args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		arr = new int[n][n];
		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]==2) {
					chicken.add(new Pair(i,j));
				}
				else if(arr[i][j]==1) {
					house.add(new Pair(i,j));
				}
			}
		}
		
		
		pickChickenHouse(0,0,new Pair[chicken.size()],new boolean [chicken.size()]);
		
		System.out.println(min);
	
	
	}
}

- 조합으로 푸는 문제이다.