BOJ_15686_치킨 배달

1. 

구분: 구현, Brute-Force

언어: Java

내 전략:

1. 치킨집이 최대 m개 있을 수 있으니, 현재 치킨집들 중에서 m개의 조합을 만들어낸다. 
2. 집들은 각각 m개의 치킨집 조합에서 자기와 가장 가까운 치킨집을 구해서 치킨 거리를 구한다. 
3. 각각의 치킨 거리를 모두 더한다. 
4. 조합 i에 대하여 i번째 치킨 거리를 큐에 저장한다. 
5. 2,3,4 과정을 반복한다. 
6. 큐에서 가장 작은 값이 정답이다. 

---

2. 코드

import java.util.*;

public class Main {
	static int m;
	static int[][] chicken;
	static int[][] house;
	static int[][] chickenComb;
	static int indexH;
	static int indexC;
	static Queue<Integer> q;
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		m = scanner.nextInt();
		
		//0번쨰집 좌표 - i, j
		house = new int[2*n][2];
		chicken = new int[13][2];
		
		q = new LinkedList<Integer>();
		
		
		int[][] map = new int[n][n];
		indexC = 0;
		indexH = 0;
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				map[i][j] = scanner.nextInt();
				//집이라면 집에 넣어 
				if(map[i][j] == 1) {
					house[indexH][0] = i;
					house[indexH][1] = j;
					indexH++;
				}
				//치킨집이라면 치킨에 넣어 
				else if(map[i][j] == 2) {
					chicken[indexC][0] = i;
					chicken[indexC][1] = j;
					indexC++;
				}
			}
		}
		//치킨 조합의 좌표들을 넣을 배열
		chickenComb = new int[m][2];

		comb(0,0);
		
		int mindist = Integer.MAX_VALUE;
		
		while(!q.isEmpty()) {
			mindist = q.peek()<=mindist? q.peek():mindist;
			q.poll();
		}
		
		System.out.println(mindist);
			

	}//main
	
	
	public static void comb(int cnt, int start) {
		//m개의 조합이 생기면 이제 return 
		if(cnt == m) {
			int sum = 0;		
			//여기서 부터 치킨거리들 합을 계산
			for(int i = 0; i<indexH; i++) {
				int min = Integer.MAX_VALUE;
				//집에서 하나 하나 꺼낸다
				int x = house[i][1];
				int y = house[i][0];
	
				//이것과 가장 가까운 치킨집을 찾아서 그 거리를 구한다. 
				for(int j = 0; j<m; j++) {
					int minx = Math.abs(x-chickenComb[j][1]); 
					int miny = Math.abs(y-chickenComb[j][0]);
					min = minx+miny <= min? minx+miny: min;
				
				}
				
				sum+=min;
			}
			
			q.offer(sum);
			return;
		}
		//치킨집 조합을 만든다
		for(int i = start; i<indexC; i++) {
			chickenComb[cnt][0] = chicken[i][0];
			chickenComb[cnt][1] = chicken[i][1];
			comb(cnt+1, i+1);
		}
			
	}//comb

}

---

3.

• 치킨집의 개수나, 집의 개수 등을 모르기 때문에 문제 조건에 따라 저장 배열을 생성하였다. - 은근히 낭비 느낌
• 처음에 조합을 구하는 부분에 실수가 있어서 문제가 해결되지 않았다. - 조합을 더 확실히 공부 
• 조합의 개수가 몇개가 나올지 몰라서 최종 sum들을 저장할 때, 큐를 사용했다. - 이런 개수 확실히 알 수 있으면 좋겠다(count변수를 추가해서 조합이 생길 떄마다 ?? 이부분은 더 생각해 보아야겠다.)
• 다른 방법들이 많은데 난 조합을 이용하여 해결하였다.