[BOJ] 백준 15686 치킨 배달

[BOJ] 

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static class Home {
		int r,c;
		Home(int r,int c){
			this.r = r;
			this.c = c;
		}
	}
	static class Chicken {
		int r,c;
		Chicken(int r,int c){
			this.r = r;
			this.c = c;
		}
	}
	static int m,size;
	static int result = Integer.MAX_VALUE;
	static boolean[] visit;
	static List<Home> homes;
	static List<Chicken> chickens;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		homes = new ArrayList<>();
		chickens = new ArrayList<>();
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				int val = Integer.parseInt(st.nextToken());
				if(val==1) homes.add(new Home(i,j));
				if(val==2) chickens.add(new Chicken(i,j));
			}
		}
		size = chickens.size();
		visit = new boolean[size];
		select(0,0);
		System.out.println(result);
	}
	private static void select(int start,int cnt) {
		if(cnt==m) {
			cal();
			return;
		}
		for(int i=start;i<size;i++) {
			visit[i] = true;
			select(i+1,cnt+1);
			visit[i] = false;
		}
	}
	private static void cal() {
		int total = 0;
		for(Home home : homes) {
			int dis = Integer.MAX_VALUE;
			for(int i=0;i<size;i++) {
				if(visit[i]) {
					Chicken chicken = chickens.get(i);
					int diff = Math.abs(chicken.r - home.r) + Math.abs(chicken.c - home.c);
					if(dis>diff) dis = diff;
				}
			}
			total += dis; 
		}
		result = Math.min(result, total);
	}
}