[백준] 15686번 : 치킨 배달 - 자바(JAVA)

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

15686번: 치킨 배달

 

문제 해석

크기가 N x N 인 도시가 존재합니다.

도시는 빈 칸, 치킨집, 집 으로 구성됩니다.

치킨 거리 = 집과 가장 가까운 치킨집 사이의 거리

도시의 치킨 거리 = 모든 집의 치킨 거리의 합

 

치킨집의 수익 증가를 위해 일부를 폐업시키려고 할 때 M개를 고르고 나머지를 모두 폐업시키려고 한다.

이 때 가장 작은 도시의 치킨 거리를 구하세요

 

문제 풀이 전 설계

조합을 통한 완전 탐색 문제 같습니다. (치킨집의 개수) C M

또한 치킨 거리를 탐색하는 도중 현재의 도시의 치킨 거리보다 커지게 되면 return하는 백트레킹을 구현합니다.

실제 구현시 백트레킹의 구현하기가 까다로워 보여 생략했습니다.

코드

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

public class Main {

	static class Pos {
		int y;
		int x;

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

		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + "]";
		}

	}

	static int[][] city;
	static int citysChickenDistance = Integer.MAX_VALUE, n, r, M, N;
	static List<Pos> chickenHouses = new ArrayList<Pos>();
	static List<Pos> personHouses = new ArrayList<Pos>();

	static final int EMPTY = 0;
	static final int HOME = 1;
	static final int CHECKEN_HOUSE = 2;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		city = new int[N][N];

		for (int y = 0; y < N; y++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int x = 0; x < N; x++) {
				city[y][x] = Integer.parseInt(st.nextToken());
				if (city[y][x] == HOME) {
					personHouses.add(new Pos(y, x));

				}
				if (city[y][x] == CHECKEN_HOUSE) {
					chickenHouses.add(new Pos(y, x));
				}
			}
		}

		// nCr
		n = chickenHouses.size();
		r = M;
		Pos[] combinatedArray = new Pos[r];
		Combination(0, 0, combinatedArray);

		System.out.println(citysChickenDistance);
	}

	private static void Combination(int cnt, int start, Pos[] combinatedArray) {
		if (cnt == r) {
			// 각각의 집을 기준으로 치킨거리를 구해야함
			int tempDistance = getCitysChickenDistance(combinatedArray);
			citysChickenDistance = tempDistance < citysChickenDistance ? tempDistance : citysChickenDistance;
			return;
		}

		for (int i = start; i < n; i++) {
			combinatedArray[cnt] = chickenHouses.get(i);
			Combination(cnt + 1, i + 1, combinatedArray);
		}

	}

	private static int getCitysChickenDistance(Pos[] combinatedArray) {

		int sum = 0;

		for (int i = 0; i < personHouses.size(); i++) {
			int min = Integer.MAX_VALUE;
			for (int j = 0; j < combinatedArray.length; j++) {
				min = Math.min(min, getChickenDistance(combinatedArray[j], personHouses.get(i)));
			}
			sum += min;
		}

		return sum;

	}

	private static int getChickenDistance(Pos cPos, Pos pPos) {
		return (Math.abs(cPos.y - pPos.y) + Math.abs(cPos.x - pPos.x));
	}

}