[15686] 치킨 배달

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

import java.util.Scanner;
import java.util.ArrayList;

class Main {
	
	static int N, M, L, len, answer;
	static int[][] arr;
	static ArrayList<House> house = new ArrayList<House>();
	static ArrayList<House> chicken = new ArrayList<House>();
	static ArrayList<House> select = new ArrayList<House>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		arr = new int[N][N];
		answer = 99999999;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				arr[i][j] = sc.nextInt();
				if(arr[i][j] == 1) house.add(new House(i, j)); 
				if(arr[i][j] == 2) chicken.add(new House(i, j));
				
			}
		}
		
		for(int i=0; i<chicken.size(); i++) select.add(new House(0, 0));
		
		for(int i=1; i<=M; i++) {
			L = i;
			combination(0, 0);			
		}
		
		System.out.println(answer);
	}
	
	public static void combination(int start, int depth) {
		if(depth == L) {	
			len = 0;
			calc();
			answer = Math.min(len, answer);
			return;
		}
		for(int i=start; i<chicken.size(); i++) {
			select.set(depth, chicken.get(i));
			combination(i+1, depth+1);
		}
	}
	
	public static void calc() {
		int min = 99999999;
		for(int i=0; i<house.size(); i++) {
			House h = house.get(i);
			min = 99999999;
			for(int j=0; j<L; j++) {
				House c = select.get(j);
				int length = Math.abs(h.x-c.x) + Math.abs(h.y-c.y);
				min = Math.min(min, length);
			}
			len += min;
		}
	}
}

class House {
	int x;
	int y;
	House(int x, int y){
		this.x=x;
		this.y=y;
	}
}

---

주어진 2차원 배열에서 0은 빈집, 1은 집, 2은 치킨집을 나타냅니다. 치킨집 중에 1개~M개를 선택하여 각각의 경우의 집까지의 치킨거리를 구해서 치킨거리의 최솟값을 구하는 문제입니다.  저는 select라는 ArrayList를 만들어서 뽑힌 치킨집을 넣고 각 경우에 치킨거리를 계산해서 최솟값을 출력하여 문제를 해결했습니다.

[ 문제 풀이 ]

1. ArrayList house 에 1로 표시된 집들을 모두 저장하고, ArrayList chicken에 2로 표시된 치킨집을 모두 저장합니다.

2. 그 다음에 모든 치킨집을 뽑았을 때 치킨거리를 계산해야하므로 뽑힌 치킨집을 넣을 ArrayList select 또한 chicken.size만큼 길이를 정해줍니다.

3. 그리고 치킨집을 1개부터 M개까지 뽑았을 경우의 각각 치킨거리를 계산하는 calc() 함수를 이용해서 최솟값을 출력하면 정답입니다.