백준 15686 치킨배달 / java 자바

www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

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

public class Main_치킨배달 {
	static int n, m, min = Integer.MAX_VALUE;
	static int[][] map;
	static ArrayList<int[]> home = new ArrayList<>();
	static ArrayList<int[]> chi = new ArrayList<>();
	static Stack<int[]> stack = new Stack<>();
	
	static void sol(int cnt, int as) {
		if (cnt == m) {
			min = Math.min(dis(), min);
			return;
		}
		for (int i = as; i < chi.size(); i++) {
			stack.push(chi.get(i));
			sol(cnt + 1, i + 1);
			stack.pop();
		}
	}
	
	static int dis() {
		int hap = 0;
		for (int[] h : home) {
			int minDis = Integer.MAX_VALUE;
			for (int[] s : stack) {
				minDis = Math.min(Math.abs(h[0]-s[0]) + Math.abs(h[1]-s[1]), minDis);
			}
			hap += minDis;
		}
		return hap;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		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) home.add(new int[] {i, j});
				else if (map[i][j] == 2) chi.add(new int[] {i, j});
			}
		}
		sol(0, 0);
		System.out.println(min);
	}
}