[백준] 15686: 치킨 배달 문제 풀이

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

이번 문제는 조합을 잘 이용하면 어렵지 않게 해결할 수 있는 문제이다.

자료구조 선언

마을의 정보를 입력 받으면서 치킨집의 갯수만큼 L 갯수를 늘려준다.
치킨집을 M개만큼 조합하기 위해 각 치킨집에 위치를 리스트에 담아준다.

static int N, M, L, ans=Integer.MAX_VALUE;
static int [][] arr, chick; // 마을의 정보와 치킨집의 조합을 담을 배열 선언
static List<int []> chickens = new ArrayList<>(); // 치킨집의 위치 정보를 담을 리스트

조합

모든 치킨집들 중에서 M개의 치킨집만 폐업하지 않고 남겨두기 때문에 M개를 고를 조합을 만든다.

static void comb(int cnt, int start) {
	if (cnt == M) {
		int sumDistance = getSumDistance();
		ans = ans>sumDistance?sumDistance:ans;
		return;
	}
	for (int i = start; i < L; i++) {
		chick[cnt] = chickens.get(i);
		comb(cnt+1, i+1);
	}
}

각 조합별 치킨거리 구하기

조합이 완성되었으면, 마을의 배열을 한칸씩 검사하면서 1이라면, 현재 위치와 폐업하지 않고 남겨둔 M개의 치킨집과의 거리 최소값을 구해 전체 distance에 합한다.

static int getSumDistance() {
	int distance = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i][j] == 1) {
				int minDist = Integer.MAX_VALUE;
				for (int c[]:chick) {
					int dist = Math.abs(c[0]-i) + Math.abs(c[1]-j);
					minDist = minDist>dist?dist:minDist;
				}
				distance+=minDist;
			}
		}
	}
	return distance;
}

위의 메서드를 통해 치킨 거리가 구해졌으면, 최소값을 갱신한다.

if (cnt == M) {
	int sumDistance = getSumDistance();
	ans = ans>sumDistance?sumDistance:ans;
	return;
}

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	static int N, M, L, ans=Integer.MAX_VALUE;
	static int [][] arr, chick;
	static List<int []> chickens = new ArrayList<>();
	static void comb(int cnt, int start) {
		if (cnt == M) {
			int distance = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (arr[i][j] == 1) {
						int minDist = Integer.MAX_VALUE;
						for (int c[]:chick) {
							int dist = Math.abs(c[0]-i) + Math.abs(c[1]-j);
							minDist = minDist>dist?dist:minDist;
						}
						distance+=minDist;
					}
				}
			}
			ans = ans>distance?distance:ans;
			return;
		}
		for (int i = start; i < L; i++) {
			chick[cnt] = chickens.get(i);
			comb(cnt+1, i+1);
		}
	}
	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());
		arr = new int [N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] == 2) {
					chickens.add(new int[] {i, j});
					L++;
				}
			}
		}
		chick = new int[M][2];
		comb(0, 0);
		System.out.println(ans);
		br.close();
	}
}