백준 15686 치킨 배달 (Java)

1. 문제 링크

15686번: 치킨 배달

 

2. 문제 및 입출력예제

 

3. 문제 풀이

치킨집 좌표를 list에 넣고 전체 치킨집 수에서 남을 M개의 치킨집을 조합한다.

조합할때마다 각 치킨집과 모든 집과의 거리(치킨거리)를 계산해서 최솟값을 합한다.

그 중 제일 작은 값을 출력한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;

class Point{
	int x;
	int y;
	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int N, M, map[][], numbers[], result;
	static ArrayList<Point> chicken, home;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		map = new int[N+1][N+1];
		chicken = new ArrayList<>();
		home = new ArrayList<>();
		numbers = new int[M];

		for(int i=1;i<N+1;i++) {
			split = br.readLine().split(" ");
			for(int j=1;j<N+1;j++) {
				map[i][j] = Integer.parseInt(split[j-1]);
				if(map[i][j] == 2) {
					chicken.add(new Point(i, j));
				}
				else if(map[i][j]==1) {
					home.add(new Point(i, j));
				}
			}
		}

		result = Integer.MAX_VALUE;
		Combination(0, 0);

		System.out.println(result);
	}
	private static void Combination(int cnt, int start) {
		if(cnt == M) {			
			int total = 0;
			for(int i=0;i<home.size();i++) {
				int min = Integer.MAX_VALUE;
				for(int j=0;j<M;j++) {
					int dis = Math.abs(home.get(i).x - chicken.get(numbers[j]).x/*chicken.get(j).x*/)
							+ Math.abs(home.get(i).y - chicken.get(numbers[j]).y);
					min = Math.min(min, dis);
				}
				total+=min;
			}
			result = Math.min(result, total);

			return;
		}
		for(int i=start;i<chicken.size();i++) {
			numbers[cnt] = i;
			Combination(cnt+1, i+1);
		}
	}
}