백준 - 15686 : 치킨 배달 [자바]

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

public class Main {
	// N*N 도시, 도시는 1*1크기의 칸으로 나누어져 있음
	// 0 : 빈 칸, 1: 집, 2 : 치킨집
	// 도시의 칸은 (r, c)와 같은 형태, r,c는 1부터 시작
	// -> 인덱스 주의
	// 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
	// 도시의 치킨 거리 : 모든 집의 치킨 거리의 합
	// 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|
	// 치킨집 최대 M개만 남기고 폐업
	// 도시의 치킨 거리가 가장 작게 되어야 한다.
	// 결과 : 도시의 치킨 거리의 최소값
	static int chickenD;
	static int[][] select;
	static List<int[]> home, chicken;
	static int d;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // N*N 도시
		int M = Integer.parseInt(st.nextToken()); // 남길 수 있는 최대 치킨집 수
		// 그러면 1~M개 괜찮은 듯

		home = new ArrayList<int[]>(); // 집
		chicken = new ArrayList<int[]>(); // chicken

		int[][] city = new int[N][N]; // 도시

		// 도시 상태
		// 1은 집이고, 2는 치킨집이니까..
		// 각각의 좌표값만 알면 되지 않을까
		// 빈칸은 그닥 필요 없을 듯.
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				// city[i][j] = Integer.parseInt(st.nextToken());
				int n = Integer.parseInt(st.nextToken());
				if (n == 1)
					home.add(new int[] { i, j });
				if (n == 2)
					chicken.add(new int[] { i, j });

			}
		}

		// 치킨 집은 조합으로 계산
		chickenD = Integer.MAX_VALUE;
		for (int i = 1; i <= M; i++) {
			select = new int[i][];
			comb(0, 0, i);
		}

		System.out.println(chickenD);
		br.close(); //
	}

	static void comb(int cnt, int start, int M) {
		if (cnt == M) {
			d = 0;
			for (int i = 0; i < home.size(); i++) {
				int[] h = home.get(i);
				int minD = Integer.MAX_VALUE;
				for (int j = 0; j < select.length; j++) {
					// 현재 집과 고른 치킨 집 사이의 거리 모두 구해서
					// 가장 가까운 치킨 집 찾기
					int[] c = select[j];
					// 집과 치킨 집 사이 거리
					int temp = Math.abs(h[0] - c[0]) + Math.abs(h[1] - c[1]);
					minD = Math.min(temp, minD);
				}
				d += minD;
			}

			chickenD = Math.min(chickenD, d);
			return;
		}

		for (int i = start; i < chicken.size(); i++) {
			select[cnt] = chicken.get(i);
			comb(cnt + 1, i + 1, M);
		}
	}
}