[BOJ 15686] 치킨배달

15686번: 치킨 배달

1) M개의 치킨집을 배치시키므로  치킨집의개수Combination M만큼 재귀를 돌아 M개의 치킨집을 배치시킨다

 

2) 치킨집을 배치시켰으면

    가) 모든 집들이

    나) 배치시킨 치킨집들에 대하여 모든 거리를 갱신시켜 최단거리를 가지도록 한다

 

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

public class A047_BJ15686_치킨배달 {
	static int N,M;

	static int[][] arr;
	static List<Coordi> Chicken = new ArrayList<>(); // 전체 치킨집의 정보 저장
	static List<Coordi> House = new ArrayList<>(); // 전체 집의 정보 저장
	static List<Coordi> SelectChicken = new ArrayList<>(); // 선택된 치킨집들만 저장
	static int res = Integer.MAX_VALUE; // 정답을 담을 변수
	static class Coordi // 해당 지점의 좌표
	{
		int x,y;
		
		public Coordi(int x, int y)
		{
			this.x=x;
			this.y=y;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
		
		N = Integer.parseInt(input[0]); // 배열의 크기
		M = Integer.parseInt(input[1]); // 배치할 수 있는 치킨집의 개수
		
		arr = new int[N][N]; 
		for (int i=0; i<N; i++)
		{
			input = br.readLine().split(" ");
			for (int j=0; j<N; j++)
			{
				arr[i][j] = Integer.parseInt(input[j]);
				
				if (arr[i][j] == 2) // 치킨집의 경우 입력
					Chicken.add(new Coordi(i,j));
				
				else if (arr[i][j] == 1) // 집의 경우 입력
					House.add(new Coordi(i,j));
			}
		}
		
		
		LocateChicken(0,0); // 치킨집을 위치시킨다
		System.out.println(res);
	}
	private static void LocateChicken(int cur, int cnt) { // 조합으로 치킨집들을 배치시킬 것이다
		
		if (cnt == M) // M개의 치킨집을 위치시켰다면
		{
			res = Math.min(res, Calculate()); // 계산하러 가본다
			return;
		}
		
		int size = Chicken.size();
		for (int i = cur; i < size; i++) // 치킨집의 개수만큼
		{
				SelectChicken.add(Chicken.get(i)); // 선택된 치킨집을 추가
				LocateChicken(i+1,cnt+1); // 재귀
				SelectChicken.remove(SelectChicken.size()-1); // 선택된 치킨집 제거
		}
	}
	private static int Calculate() {
		
		int size = House.size(); // 집의 개수
		int TotalMinDist = 0; // 치킨집 배치했을 때 최솟값을 가질 변수
		
		for (int i=0; i < size; i++) // 각각의 집들이
		{
			Coordi Customer = House.get(i); //i번째 집을 픽하고
			int mindist = Integer.MAX_VALUE; // 최댓값을 가지게 한다음
			for (int j=0; j <M; j++) // 치킨집의 개수만큼 반복하여 가장 거리가 짧은 치킨집을 선택하도록
			{
				Coordi Chick = SelectChicken.get(j); // j번째 치킨집을 고르고
				mindist = Math.min(mindist, Math.abs(Customer.x - Chick.x) + Math.abs(Customer.y - Chick.y));
				// 가장 거리가 짧은 치킨집의 최솟거리를 갱신한다
			}
			TotalMinDist += mindist; // 최솟값들을 누적하여
		}
		
		return TotalMinDist; // 최솟값을 반환한다.
		
	}

	
	
}