백준 : 15686

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

15686번: 치킨 배달

 

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

public class B15686 {

	static int[][] map;
	static int N, M;
	static int houseNum = 0, chkenNum = 0;
	static int MinmumValue = 987654321;
	static boolean[] check;
	static Chiken[] house;
	static Chiken[] chiken;
	
	public static class Chiken {
		int y;
		int x;

		Chiken(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		house = new Chiken[N * 2];
		chiken = new Chiken[13];
		check = new boolean[13];
		int a = 0;

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				a = Integer.parseInt(st.nextToken());
				if (a == 1) {
					// 집
					house[houseNum++] = new Chiken(i,j);

				} else if (a == 2) {
					// 치킨
					chiken[chkenNum++] = new Chiken(i,j);
				}
			}
		}
		
		DFS(0,0);
		System.out.println(MinmumValue);

	}

	private static void DFS(int start, int count) {
		// TODO Auto-generated method stub
		
		if(count == M) {
			ArrayList<Chiken> myChiken = new ArrayList<Chiken>();
			for(int i=0;i<chkenNum;i++) {
				if(check[i]) {
					myChiken.add(new Chiken(chiken[i].y,chiken[i].x));
				}
			}
			int sum=0;
			
			for(int i =0;i<houseNum;i++) {
				int myMin = 987654321;
				for(int j=0;j<M;j++) {
					int s = Math.abs(house[i].x - myChiken.get(j).x)
							+ Math.abs(house[i].y - myChiken.get(j).y);
					
					myMin = Math.min(myMin, s);
				}
				sum += myMin;
			}
			
			MinmumValue = Math.min(MinmumValue, sum);
			return;
		}
		
		
		
		for(int i=start;i<chkenNum;i++) {
			if(check[i]) continue;
			
			check[i] =true;
			DFS(i+1,count+1);
			check[i] = false;
		}
		
		
	}
}