[BOJ 15686] 치킨 배달

문제

• BOJ 15686
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

한달전에 한번 풀었던 문제라 쉽게 풀린 문제였다.
전체 치킨집 중 M개를 뽑은 각 경우의 수에서 집으로 부터 치킨거리를 구하고 이를 합한 도시의 치킨거리를 순서대로 구하면 된다.
M개를 뽑는데는 조합을 사용하였다. 조합은 브루트포스에서 많이 사용되므로 반드시 코드를 이해+암기해두자!!
생성된 경우의 수는 전체 치킨 리스트의 인덱스를 나타내므로 각 집으로 부터 치킨거리를 구할때는 반드시 chickens.get(numbers[j])에 접근해야 한다. 다 구해놓고 아무 생각없이 chickens.get(j)해서 헤맸음… 집중.. 또 집중할 것!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Boj15686 {
	static ArrayList<Point> homes; //집 좌표 담을 배열
	static ArrayList<Point> chickens; //치킨 좌표 담을 배열
	static int[] selected; //뽑은 경우의 수
	static int[] numbers; //전체 인덱스
	static int N, M;
	static StringTokenizer st;
	static int Ans = Integer.MAX_VALUE; //최소가 되는 도시의 치킨거리
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		homes = new ArrayList<>();
		chickens = new ArrayList<>();
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				int input = Integer.parseInt(st.nextToken());
				if(input == 1) homes.add(new Point(i, j));
				if(input == 2) chickens.add(new Point(i, j));
			}
		}
		
		Ans = Integer.MAX_VALUE;
		selected = new int[M];
		numbers = new int[chickens.size()];
		for(int i=0; i<chickens.size(); i++) numbers[i] = i;
		
		comb(0, 0); //전체 치킨집 중 M개 뽑기(조합)
		System.out.println(Ans);
	}
	
	private static void comb(int cnt, int cur) {
		if(cnt == M) { //경우의 수를 구했으면
			int cityLength = 0;
			for(int i=0; i<homes.size(); i++) { //모든 집을 돌면서
				Point home = homes.get(i);
				int chickenLength = Integer.MAX_VALUE; //치킨거리
				for(int j=0; j<selected.length; j++) { //각 집에서 치킨거리(최소거리) 구하기
					Point chicken = chickens.get(selected[j]);
					int dist = getDistance(home.x, home.y, chicken.x, chicken.y);
					chickenLength = Math.min(chickenLength, dist);
				}
				cityLength += chickenLength; // 모든 집의 치킨거리 누적합 = 도시의 치킨거리
			}
			Ans = Math.min(Ans, cityLength);
			return;
		}
		
		for(int i=cur; i<chickens.size(); i++) {
			selected[cnt] = numbers[i];
			comb(cnt+1, i+1);
		}
	}

	private static int getDistance(int x1, int y1, int x2, int y2) {
		return Math.abs(x1-x2)+Math.abs(y1-y2);
	}

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