[BOJ] 치킨 배달

[15686] 치킨 배달

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

• 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.
• 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
• 도시의 치킨집 중 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시키려 한다.
• 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오

 

 

Solution

• permutation()으로  치킨집 중 M개만 골라 치킨거리를 계산한다.

 

 

소스코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int n, m, min;
	static int[] a, temp;
	static List<Node> chicken;
	static List<Node> home;

	static class Node {
		int x, y;

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

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringTokenizer st = new StringTokenizer(sc.nextLine());
		n = stoi(st.nextToken());
		m = stoi(st.nextToken());
		init();
		int count = 0;
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(sc.nextLine());
			for (int j = 1; j <= n; j++) {
				int info = stoi(st.nextToken());
				if (info == 1) {
					home.add(new Node(i, j));
				} else if (info == 2) {
					chicken.add(new Node(i, j));
					count++;
				}
			}
		}
		min = Integer.MAX_VALUE;
		permutation(0, 0, count);
		System.out.println(min);

	}

	public static void simulation() {
		int sum = 0;
		for (int i = 0; i < home.size(); i++) {
			int pick = Integer.MAX_VALUE;
			for (int j = 0; j < a.length; j++) {
				int temp = Math.abs(home.get(i).x - chicken.get(a[j]).x)
						+ Math.abs(home.get(i).y - chicken.get(a[j]).y);
				pick = Math.min(pick, temp);
			}
			sum += pick;
		}
		min = Math.min(min, sum);
	}

	public static void permutation(int depth, int start, int size) {
		if (depth == m) {
			simulation();
			return;
		}
		for (int i = start; i < size; i++) {
			a[depth] = i;
			permutation(depth + 1, i + 1, size);
		}
	}

	public static void init() {
		chicken = new ArrayList<>();
		home = new ArrayList<>();
		a = new int[m];
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}