BJ15686 치킨 배달

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

조합으로 M개의 치킨집을 고르고, 각 집마다 가장 가까운 치킨집을 찾아 치킨거리에 더해주면 된다.

package day0223;

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

public class DeliverChicken {
	static int N, M, numofChicken = 0, numofHouse = 0, answer = Integer.MAX_VALUE;
	static int[] numbers;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static ArrayList<House> houseList;
	static ArrayList<Chicken> chickenList;
	public static class House{ 
		int x, y;
		public House(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	public static class Chicken extends House{
		public Chicken(int x, int y) {
			super(x, y);
		}
	}
	public static void combination(int cnt, int start) { // M개의 치킨집을 선정해서 계산해보기.
		if(cnt == M) {
			int sum = 0;
			for(House h : houseList) { // 선택된 M개의 치킨집과 집들의 치킨거리 합 계산.
				sum += calcDist(h, numbers);
			}
			if(sum < answer) answer = sum;
			return;
		}
		for(int i = start; i < chickenList.size(); i++) {
			numbers[cnt] = i;
			combination(cnt + 1, i + 1);			
		}
	}
	public static int calcDist(House h, int[] numbers) { // 집과 가장 가까운 치킨집의 거리 계산.
		int min_dist = Integer.MAX_VALUE;
		int dist;
		for(int i = 0; i < M; i++) {
			dist = Math.abs(chickenList.get(numbers[i]).x - h.x) + Math.abs(chickenList.get(numbers[i]).y - h.y);
			if(dist < min_dist) min_dist = dist;
		}
		return min_dist;
	}
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		houseList = new ArrayList<>();
		chickenList = new ArrayList<>();
		numbers = new int[M];
		for (int i = 0; i < N; i++) { // 입력을 받으며, 집과 치킨집의 좌표를 각각 리스트에 추가.
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				int tmp = Integer.parseInt(st.nextToken());
				if (tmp == 1) {
					houseList.add(new House(i, j));
				} else if (tmp == 2) {
					chickenList.add(new Chicken(i, j));
				}
			}
		}
		combination(0, 0);
		bw.append(Integer.toString(answer));
		bw.flush();
	}
}