백준 알고리즘 - 15686 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

  이번 문제는 백준 알고리즘의 15686번 문제인 '치킨 배달' 문제입니다.

 

 

  N x N 크기인 마을이 있는데 여기에는 1로 표시되는 가정집과 2로 표시되는 치킨집이 존재합니다. 그런데 이 마을에서는 치킨을 너무나도 좋아하는 나머지 각자의 집에서 제일 최단거리인 치킨집까지의 거리를 '치킨 거리'라고 일컫는답니다. 그런데 이 마을에 있는 모든 치킨집은 같은 프렌차이즈여서 효율을 극대화하기 위해 M개까지 치킨집을 줄인다고 하네요. 이 때, 마을 안에 존재하는 모든 가정집의 치킨 거리가 '최소화'되는 M개의 치킨집을 구해 마을 전체의 치킨 거리의 합을 구하는 문제입니다.

 

아... 참으로 평화로운 마을이네요. 치킨으로 하나가 되는 마을이라니 한국 어딘가에 있을 법하지 않나요? 하하

 

 

  난이도가 골드V여서 겁먹었었는데, 알고보면 별거 아닌 문제입니다.

원래 있는 전체 치킨집 크기를 K라고 했을 때, K개 중에 M개를 순서 없이 골라 각 가정집들과 치킨집들 사이의 최소 거리의 합을 구해, 그 값이 최소가 되는 지점을 찾아 출력해주면 됩니다. 

 

  그렇다면 이 문제에서 주요 포인트는

1. 조합 알고리즘 짜기.

2. 각 조합에서 가정집들과 치킨집들 사이의 최소 거리 구하기.

  이 정도이겠군요.

 

 

  제 코드에서 특이한 점은 제가 최근에 배운 조합 알고리즘을 사용했다는 점인데요. nextPermutation 알고리즘을 응용하여 한번 실행할 때마다 조합이 추출되는 nextCombination을 사용했습니다. 사실 해당 method 자체는 nextPermutation과 다른 점이 하나도 없고, 들어가는 배열이 {1, 2, 3, 4, 5} 이런게 아니라 {0, 0, 0, 1, 1}과 같이 0으로 초기화 되어있는 배열에 끝에서부터 M의 갯수만큼 1로 초기화시킨 배열을 사용했다는 점입니다.

 

 

  저도 아직 정확하게 이해하고 사용한 것은 아니지만 실제로 동작하고, 하나씩 진행되는 조합을 볼 수 있다는 점에서 쓰기 편한 알고리즘인 것 같네요. 여러분들도 한번씩 사용해보시는걸 추천드립니다.

 

 

 

  아래는 제 문제 풀이 코드입니다.

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

public class Main_BJ_15686_치킨배달 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
		
		// N : 지도의 크기는 N*N
		// M : 남길 치킨집 개수
		int N = Integer.parseInt(tk.nextToken());
		int M = Integer.parseInt(tk.nextToken());
		
		// houseList : 집의 위치를 모아놓은 ArrayList
		// chickenList : 치킨집의 위치를 모아놓은 ArrayList
		ArrayList<Integer[]> houseList = new ArrayList<Integer[]>();
		ArrayList<Integer[]> chickenList = new ArrayList<Integer[]>();
		
		// 입력을 받아가면서 1을 받을 경우 해당 i, j가 집의 위치이므로 houseList에,
		// 2를 받을 경우 해당 i, j가 치킨집의 위치이므로 chickenList에 넣는다.
		for(int i = 0; i < N; i++) {
			tk = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				int temp = Integer.parseInt(tk.nextToken());
				if(temp == 1) {
					Integer[] house = {i, j};
					houseList.add(house);
				}
				if(temp == 2) {
					Integer[] chicken = {i, j};
					chickenList.add(chicken);
				}
			}
		}
		
		// isSelected : 이 배열의 맨 끝부터 M개만큼 1을 채워놓고 nextPermutation 알고리즘을 돌리면 조합이 하나씩 나옴.
		// 이때, isSelected의 크기는 치킨집의 개수
		int[] isSelected = new int[chickenList.size()];
		for(int i = chickenList.size()-1; i > chickenList.size() - M - 1; i--) {
			isSelected[i] = 1;
		}
		
		// wholeMin : 마지막에 출력할 제일 작은 치킨 거리.
		int wholeMin = Integer.MAX_VALUE;
		
		// 한번 makeCombination을 돌릴 때마다 각 집에서 조합으로 뽑힌 치킨집과의 거리 중 가장 작은 값을 min에 넣고
		// 그 값들의 합산을 sum에 넣은 뒤 그게 전체적으로도 가장 작은 치킨 거리인지 확인.
		do {
			int sum = 0;
			for(int i = 0; i < houseList.size(); i++) {
				Integer[] house = houseList.get(i);
				int min = Integer.MAX_VALUE;
				for(int j = 0; j < chickenList.size(); j++) {
					if(isSelected[j] == 1) {
						Integer[] chicken = chickenList.get(j);
						min = Math.min(min, Math.abs(chicken[0] - house[0]) + Math.abs(chicken[1] - house[1]));
					}				
				}
				sum += min;
			}
			wholeMin = Math.min(wholeMin, sum);
		}while(makeCombination(isSelected, chickenList.size()));
		
		// 답 출력.
		System.out.println(wholeMin);
	}

	// nextPermutation 알고리즘을  1이 M개 있는 0과 1로 이루어진 배열로 돌림으로써 조합을 하나씩 추출해냄.
	public static boolean makeCombination(int[] isSelected, int N) {
		
		int i = N - 1;
		while(i > 0 && isSelected[i-1] >= isSelected[i]) i--;
		if(i == 0) return false;
		
		int j = N - 1;
		while(isSelected[i-1] >= isSelected[j]) j--;
		swap(isSelected, i-1, j);
		
		int k = N - 1;
		while(i < k) swap(isSelected, i++, k--);
		
		return true;
	}
	
	// isSelected 안에 있는 i번째 값과 j번째 값의 위치를 변경.
	public static void swap(int[] isSelected, int i, int j) {
		int temp = isSelected[i];
		isSelected[i] = isSelected[j];
		isSelected[j] = temp;
	}
}