백준 : 15686 치킨배달

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

15686번: 치킨 배달

//comb(0,0)시작
//nCm임 (n==전체 치킨집수, m=선택된치킨집 수)
//1.n크기의 체크배열 생성
//2.for( i= 0~n-1)
// check[i]=true
// comb(i,cnt+1)
// check[i]=false;
//3.if(cnt==M) 할일(완성된조합, 체크되면->계산), 리턴

 

check배열 idx와 치킨리스트 idx는 맞추어져있음

할일 :

for(home h : homes)

for(int i=0~치킨사이즈)

if(check[i])

h[0]-chickens.get(i)[0] ............ //차이계산

static void comb(int idx, int cnt)
	{
		if(cnt==M)
		{
			calc();		//조합완성시 할일들
			return;
		}
		
		for(int i=idx+1;i<check.length;++i)
		{
			check[i]=true;
			comb(i,cnt+1);
			check[i]=false;
		}
	}

 

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

public class Main_15686_유동훈 {
	static int N;
	static int M;
	static int[][] map;
	static List<int[]> chickens;
	static List<int[]> homes;
	static int answer=Integer.MAX_VALUE;
	static boolean[] check;
	static int[] result;
	
	static List<int[]> union(List<int[]> list1, int[] is)
	{
		List<int[]> joined=new ArrayList<int[]>();
		joined.addAll(list1);	//joined  안쓰고 list1쓰기/???
		if(is[0]!=-1) joined.add(is);
		return joined;
		
	}
	static void calc()
	{
		int dist=0;
		
		 for (int[] h : homes) {
             int tmp = Integer.MAX_VALUE;
             for (int i = 0; i < chickens.size(); i++) {
                 if (check[i])
                     tmp = Math.min(tmp, Math.abs(h[0] - chickens.get(i)[0]) + Math.abs(h[1] - chickens.get(i)[1]));
             }
             dist += tmp;
         }
         answer = Math.min(answer, dist);
		//answer=result;
		//return result;

	}
	/*static void sol(List<int[]> m_chickens,int depth, int m, int not_select)
	{
		if(cnt>=1)
		{
			answer=Math.min(answer, calc(m_chickens));
		}
		if(m_chickens.size()==m)
		{
			//answer=Math.min(answer, calc(m_chickens));
			calc(m_chickens);
			return;
		}
		//가지치기
		//치킨집수-not_select수<선택해야되는 수 -> ~유망 -> 가지치기
		if(chickens.size()-not_select < m)
		{
			return;
		}
		if(depth==m && m>0)
		{
			return;
		}
		
		
		
		if(select==m)
		{
			answer=Math.min(answer, calc(m_chickens));
			return;
		}
		
		//for문 => 트리의 루트를 1,2,3,4.. 일때 각각 한번씩해줌
		//for문 없으면 루트가 1로 고정.
		for(int i=0; i<chickens.size();++i)
		{
			sol(union(m_chickens,chickens.get(i)),depth+1,m,not_select); 
			
			sol(union(m_chickens,new int[] {-1,-1}),depth+1,m,not_select+1); 
		}
		
		
	}*/
	
	//comb(0,0)시작
	//nCm임 (n==전체 치킨집수, m=선택된치킨집 수)
	//1.n크기의 체크배열 생성
	//2.for(0~n-1)
	//		check[i]=true
	//		comb(i,cnt+1)
	//		check[i]=false;
	//3.if(cnt==M) 할일, 리턴
	static void comb(int idx, int cnt)
	{
		if(cnt==M)
		{
			calc();		//조합완성시 할일들
			return;
		}
		
		for(int i=idx+1;i<check.length;++i)
		{
			check[i]=true;
			comb(i,cnt+1);
			check[i]=false;
		}
	}
	

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());
        StringBuilder sb= new StringBuilder();
        
        map=new int[N][N];
        homes = new ArrayList<int[]>();
        chickens = new ArrayList<int[]>();
        for(int i=0;i<N;++i)
        {
        	st = new StringTokenizer(br.readLine());
        	for(int j=0;j<N;++j)
        	{
        		map[i][j]=Integer.parseInt(st.nextToken());
        		if(map[i][j]==1)
        		{
        			homes.add(new int[] {i,j});
        		}
        		else if(map[i][j]==2)
        		{
        			chickens.add(new int[] {i,j});
        		}
        	}
        }
        //입력 끝
        
        /*List<int[]> m_chickens=new ArrayList<int[]>();
        for(int i=1;i<=M;++i)
        {
        	 sol(m_chickens,0,i,0);
        }*/
        
        check= new boolean[chickens.size()];
        comb(-1,0);
        //comb2(0,0);
        
        sb.append(answer);
        System.out.println(sb);

	}

}