[알고리즘] 백준15686 - 치킨배달 java

package a0223;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
 
 남겨질 가게의 개수 = M -> 조합으로 완탐 
 조합 정해질때마다 bfs돌리기 
 
 */




public class 백준_치킨배달 {

	static ArrayList<int[]> home;
	static ArrayList<int[]> chicken ;
	static int remain;
	static int size;
	static int[][] arr; 
	static int minnum = Integer.MAX_VALUE;
	static int result[];
	static int tmp[][];
	static int[][] visit;
	static int minlen = Integer.MAX_VALUE;
	static int nownum = 0;
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	
	static boolean check(int i, int j) {
		if(0<=i&&i<size && 0<=j&&j<size)return true;
		return false;
	}
	
	static int lencheck(int cnt) {
		int nowlen = 0;
		int lensum = 0;
		
		for(int i=0; i<home.size(); i++) {
			int nowhi = home.get(i)[0];
			int nowhj = home.get(i)[1];
			minlen = Integer.MAX_VALUE;
			
			for(int j=0; j<cnt; j++) {
				int cidx = result[j];
				int nowci = chicken.get(cidx)[0];
				int nowcj = chicken.get(cidx)[1];
				nowlen = Math.abs(nowhi-nowci) + Math.abs(nowhj-nowcj);
				minlen = Math.min(nowlen, minlen);
			}
			//System.out.println("nowhi:"+nowhi+" nowhj:"+nowhj+"minlen:"+minlen);
			lensum+=minlen;
		}
			
		return lensum;
	}
	
	static void find(int cnt, int idx) {
		
//		for(int i=0; i<cnt; i++)System.out.print(result[i]+" ");
//		System.out.println();
		
		nownum =lencheck(cnt);
		//System.out.println("nowlen:" + nownum);
		minnum = Math.min(nownum, minnum);
		
		if(cnt == remain) {
			return;
		}
		
		for(int i=idx+1; i<chicken.size(); i++) {
			result[cnt] = i;
			find(cnt+1, i);
		}
	}
	
	
	public static void main(String[] args) throws Exception {
		
		//Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		size = Integer.parseInt(st.nextToken());
		remain = Integer.parseInt(st.nextToken());
		arr = new int[size][size];
		result = new int[remain];
		
		home = new ArrayList<>();
		chicken = new ArrayList<>();
		
		
		for(int i=0; i<size; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<size; j++) {
				arr[i][j] = st.nextToken().charAt(0)-'0';
				if(arr[i][j]==1)home.add(new int[] {i,j});
				else if(arr[i][j]==2)chicken.add(new int[] {i,j});
			}
		}
		
		for(int i=0; i<chicken.size(); i++) {
			result[0] = i;
			find(1, i);
		}
		System.out.println(minnum);
	}

}