[Java] BOJ15686_치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

M개의 치킨집을 골라 도시의 치킨 거리를 가장 작게 만드는 경우를 구하는 구현 문제이다.

M보다 크거나 같은 치킨집의 수에서 M개를 고르는 조합으로 해결하였다. 

 

M개의 치킨집을 고른 후 각 집에서 치킨집들까지 거리 중 가장 작은 값들을 더해 해당 경우의 치킨 거리를 구했다.

그 후 최솟값 비교를 통해 결과를 도출했다.

 

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

public class Main {
	
	static List<City> chicken = new ArrayList<>();
	static List<City> house = new ArrayList<>();
	static int M;
	static int min = Integer.MAX_VALUE;
	static int res = Integer.MAX_VALUE;
	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());
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int temp = Integer.parseInt(st.nextToken());
				if(temp==2) chicken.add(new City(i+1, j+1));
				if(temp==1) house.add(new City(i+1, j+1));
			}
		}
		combination(0, new int[M], 0);
		System.out.println(res);
	}

	static void combination(int cnt, int[] result, int startIdx) {
		
		if(cnt==M) {
			int sum = 0;
			for(int i = 0,size = house.size(); i < size; i++) {
				min = Integer.MAX_VALUE;
				for (int j = 0; j < cnt; j++) {
					min = Math.min(min, Math.abs(house.get(i).r - chicken.get(result[j]).r) + 
							Math.abs(house.get(i).c - chicken.get(result[j]).c));
				}
				sum += min;
			}
			res = Math.min(res, sum);
			return;
		}
		
		for(int i = startIdx,size = chicken.size(); i < size; i++) {
			result[cnt] = i;
			combination(cnt+1, result, i+1);
		}
	}
	
	static class City{
		int r, c;
		
		public City(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
}