BOJ - 15656 ) 치킨 배달

 

---

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

15686번: 치킨 배달

---

Map정보에서 최대 M개의 치킨집만 남기고 폐업을 할예정에서, 집과 남겨진 치킨집 사이의 최솟값을 구하는 문제이다.

 

딱 봐도, 특별한 공식이 보이지 않으므로 완전탐색을 해야한다.

 

굳이 map을 선언하지 않고도, arraylist에 좌표값을 저장해서 풀수있을것 같았다.

 

알고리즘은 다음과 같다.

 

1 ) 입력으로부터 집, 치킨집의 좌표를 받는다.

 

2 ) 치킨집의 좌표에서 M개 이하의 부분집합셋을 만든다 ( 조합 )

 

3 ) 선택된 M개 이하의 치킨집과 집들사이의 거리의 최솟값을 구한다.

 

4 ) 중간중간 기존에 구했던 답보다 커지면 가지치기를 해준다 ( 백트래킹 )

 

5 ) 최종 선택된 답이 거리의 최솟값이다.

 

---

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

public class Main {
	static int map[][],n,m,tmp,cnt,ny,nx,mindist,res ,ans = 987654321;
	static ArrayList<int []> Home = new ArrayList<>();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int Chicken[][] = new int[13][2] , index=0;
		
		for(int y = 0 ; y< n ; y++) {
			st = new StringTokenizer(br.readLine());
			for(int x = 0 ; x< n ; x++) {
				tmp = Integer.parseInt(st.nextToken());
				if(tmp ==1) {
					Home.add(new int[] {y,x});
				
				}else if(tmp == 2) { 
					
					Chicken[index][0] = y;
					Chicken[index][1] = x;
					index++;
				}
			}
		}
		int Chicken_Co[][] = new int[index][2];
		for(int y = 0 ; y< index ; y++) {
			for(int x= 0 ; x < 2 ;x++) {
				Chicken_Co[y][x] =Chicken[y][x];
			}
		}
		int choice[] = new int[index];
		for(int i = 1 ,size = (1<<index) ; i < size ; i++) {
			cnt = 0; 
			for(int j = 0 ; j < index ; j ++) {
				if((i & (1<<j)) != 0 ) {
					choice[j] =1;
					cnt++;
				}
				else choice[j]= 0;
			}
			if(cnt >0 && cnt <= m) {
				int hsize = Home.size();
				for(int k = 0 ; k < hsize ;  k++) {
					ny = Home.get(k)[0];
					nx = Home.get(k)[1];
					mindist = 987654321;
					for(int j = 0 ; j < index ; j++) {
						if(choice[j] ==1) {
							int temp = distance(nx, ny, Chicken_Co[j][1], Chicken_Co[j][0]);
							mindist = mindist > temp ? temp : mindist;
						}
					}
					res +=mindist;
					if(ans < res) break;
				}
			}
			if(res != 0 && ans > res) ans = res;
			res = 0;
		}
		System.out.print(ans);
	
	}
	public static int distance(int x1,int y1, int x2, int y2) {
		return Math.abs(x1-x2) + Math.abs(y1-y2);
	}
}

---