[문제] 백준 15686번 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

풀이

 

처음에 배열을 할당해서 풀었는데, 다시 풀어보니 치킨집과 집 위치만 저장하는 arraylist만 만들면 배열이 필요없음을 알았다.

'폐업시키지 않을' 치킨집의 최대 개수가 M개 이므로, 살아남을 수 있는 치킨집의 개수는 1~M개이다.

(처음에 폐업시키는 치킨집이 M개인줄 알고 삽질했었다. 문제를 두번 세번!! 제대로 읽자!!!!!)

 

그래서 1~M개에 대하여 조합을 발생키면 된다. (부분집합으로 풀어서 공집합만 제외해줘도 된다.)

 

또한, 해당 집의 기준으로 치킨거리는 가장 가까운 치킨집과의 거리니까 아래 코드와 같이 최소값을 계속 갱신해주면 된다!

 

문제를 제대로 이해하면서 읽자! 제대로 안읽어서 여러번 틀렸다. (치킨거리, 도시치킨거리, 폐업최대,, 등등)

public class BOJ_15686_2 {
	static int N, M;
	static ArrayList<int[]> chicken = new ArrayList<>(); // 치킨집 위치 저장
	static ArrayList<int[]> house = new ArrayList<>(); // 집 위치 저장
	static int min = Integer.MAX_VALUE;	//최종 치킨 거리 구하기

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());	//크기
		M = Integer.parseInt(st.nextToken());	// 살아남는 치킨 가게 최대 개수

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < N; j++) {
				int loc = Integer.parseInt(st.nextToken());
				if(loc == 1) {
					house.add(new int[] {i,j});
				}
				if (loc == 2)	// 치킨가게 위치 저장해주기
					chicken.add(new int[] { i, j });
			}
		}
		
		for(int i=1;i<=M;i++) {	// 1게부터 M개까지의 치킨가게가 살아남을 때
			comb(i, 0, new int[i], 0);
		}
		System.out.println(min);
	}
//	조합, remain: 선택 개수
	static void comb(int remain, int cnt, int[] selected, int startIdx) {
		if (cnt == remain) {
			int distance = 0;
			for(int i=0;i<house.size();i++) {
				int hx = house.get(i)[0];
				int hy = house.get(i)[1];
				int minD= Integer.MAX_VALUE;
				
				for(int j=0;j<remain;j++) {
					int idx = selected[j];
					int cx = chicken.get(idx)[0];
					int cy = chicken.get(idx)[1];
					int dis =  (Math.abs(cx - hx) + Math.abs(cy - hy));//집과 선택된 치킨집까지의 거리
					minD = Math.min(dis, minD);	// 치킨 거리- 가장 가까운 치킨집과의 거리=> 최소갱신
				}
				distance += minD;	//도시의 치킨거리: 모든 집의 치킨거리 누적
			}
			
			min = Math.min(min, distance);	// 최소값 갱신
			return;
		}
		
		for (int i = startIdx; i < chicken.size(); i++) {
			selected[cnt] = i;
			comb(remain, cnt + 1, selected, i + 1);
		}
	}
}