[JAVA] 백준 15686 치킨 배달

전체 코드

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

public class 백준_15686_치킨배달 {

	static int N, M, MIN = Integer.MAX_VALUE, size;

	static class Point { // 좌표 저장용 클래스
		int y;
		int x;

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

	static ArrayList<Point> chks; // 치킨집들
	static ArrayList<Point> homes; // 가정집들
	static int[] nums, sel; // 조합에 쓰일 배열들

	public static void main(String[] args) throws IOException {
		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 tmp;
		
		chks = new ArrayList<Point>(); //치킨집과 가정집을 ArrayList로 준비한다.
		homes = new ArrayList<Point>();

		for (int i = 0; i < N; i++) { // 위치들은 Point클래스에 담기므로 따로 배열에 저장하지 않는다.
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				tmp = Integer.parseInt(st.nextToken());
				if (tmp == 2) { //값이 2면 치킨집에 좌표를 저장하고, 1이면 가정집에 저장한다.
					chks.add(new Point(j, i));
				} else if (tmp == 1) {
					homes.add(new Point(j, i));
				}
			}
		}
		
		size = chks.size(); // 밑에서 자주쓰일 치킨집 사이즈

		nums = new int[size];
		sel = new int[M];

		for (int i = 0; i < size; i++) {
			nums[i] = i; // 치킨집 사이즈 만큼 0~size-1까지 초기화 해준다 (인덱스 역할)
		}

		combination(0, 0); // 조합 시작

		System.out.println(MIN);

	}

	public static void combination(int idx, int k) { 
		if (k == M) { // 배열 중 중복되지 않는 M개의 치킨집을 고른다.
			int sum = 0;
			for (Point home : homes) {
				sum += getMin(sel, home); // 고른 치킨집들과 가정집들 간의 전체 최소거리를 구하고
			}
			if (MIN > sum) { // 모든 조합들 중 최소값을 구한다.
				MIN = sum;
			}
			return;
		}

		if (idx == size)
			return;

		sel[k] = nums[idx];
		combination(idx + 1, k+1);
		combination(idx + 1, k);

	}

	public static int getMin(int[] idxs, Point home) {
		int min = Integer.MAX_VALUE, tmp;

		for (int idx : idxs) { // 조합에서 들어온 인덱스의 치킨집들 중 집 하나와의 거리가 가장 가까운 것을 리턴한다.
			Point chk = chks.get(idx);
			tmp = Math.abs(home.y - chk.y) + Math.abs(home.x - chk.x);
			if (min > tmp) {
				min = tmp;
			}
		}

		return min;
	}

}

 

문제 핵심 코드

public static void combination(int idx, int k) { 
	if (k == M) { // 배열 중 중복되지 않는 M개의 치킨집을 고른다.
		int sum = 0;
		for (Point home : homes) {
			sum += getMin(sel, home); // 고른 치킨집들과 가정집들 간의 전체 최소거리를 구하고
		}
		if (MIN > sum) { // 모든 조합들 중 최소값을 구한다.
			MIN = sum;
		}
		return;
	}

	if (idx == size)
		return;

	sel[k] = nums[idx];
	combination(idx + 1, k+1);
	combination(idx + 1, k);

}

public static int getMin(int[] idxs, Point home) {
	int min = Integer.MAX_VALUE, tmp;

	for (int idx : idxs) { // 조합에서 들어온 인덱스의 치킨집들 중 집 하나와의 거리가 가장 가까운 것을 리턴한다.
		Point chk = chks.get(idx);
		tmp = Math.abs(home.y - chk.y) + Math.abs(home.x - chk.x);
		if (min > tmp) {
			min = tmp;
		}
	}

	return min;
}

 

조합을 적절히 이용하면 아주 쉬운 문제였다! 치킨집들의 조합과 최소 거리를 구하는 부분을 잘 캐치했으면 충분히 가능했을 것이다.