[BOJ] - 치킨 배달 / 15686번 (Java)

[BOJ] - 치킨 배달 / 15686번 (Java)

[BOJ] - 치킨 배달 / 15686번 (Java)

1. 문제 접근

0, 1(고객의 집), 2(치킨 집)으로 이루어진 도시의 정보를 입력 받았을 때, 각 고객의 집으로부터 거리의 합이 최소가 되는 M개의 치킨집을 선택하는 문제다.

 

입력값을 보면 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)으로 M의 최대 값이 13이고, 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다는 말이 있다.

 

따라서 주어지는 치킨집은 최대 13개, M은 13보다 작거나 같다고 정리할 수 있다.

 

치킨집의 개수가 최대 13개라는 것은 13 Combination 6 or 7을 해도 경우의 수가 1,716개 밖에 되지 않는다. 

 

따라서 조합을 통해 선택할 치킨 집을 구한 뒤, 모든 고객의 집에 대해 최소 거리를 구하면 된다.

 

// 각 집에서 모든 치킨집까지의 거리 중 최소값을 더한다.
for (Pos client : clientPos) {
    // 개인에 대한 치킨집까지의 최소거리
    int personalDist = Integer.MAX_VALUE;
    for (int idx = 0; idx < M; ++idx) {
        // 현재 살펴볼 치킨 집
        Pos chicken = chickenPos[selected[idx]];
        // 이전에 계산한 치킨집에 대한 거리와 비교
        personalDist = Math.min(personalDist,
                Math.abs(client.x - chicken.x) + Math.abs(client.y - chicken.y));
    }
    // 도시 치킨거리에 개인 치킨거리 합산
    localDistSum += personalDist;
}
// 최소값 선택
ans = Math.min(ans, localDistSum);

 

---

2. 코드

package boj;

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

/**
 * [BOJ] - 치킨 배달 / 15686번 
 * @author JinHxxxxKim
 * 
 * 1. N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)을 입력받는다.
 * 2. 도시의 정보를 입력받는다.
 * 		- 치킨집의 정보, 집의 정보를 별도로 저장한다.
 * 3. 총 치킨집의 수 중에서 M개의 치킨집을 선택한다.(조합)
 * 4. Combination
 * 		- selectIdx == M or elementIdx == 치킨집의 총 개수 (기저조건)
 * 			- 각 집까지의 거리의 합을 구하고 갱신한다.
 */
public class Sol_15686 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	private static int N, M;
	private static Pos[] chickenPos;
	private static Pos[] clientPos;
	private static int[][] map;

	private static int chickenNum;
	private static int clientNum;

	private static int[] selected;
	private static int ans;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine().trim());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];

		for (int row = 0; row < N; ++row) {
			st = new StringTokenizer(br.readLine().trim());
			for (int col = 0; col < N; ++col) {
				map[row][col] = Integer.parseInt(st.nextToken());
				if (map[row][col] == 1) {
					++clientNum;
				} else if (map[row][col] == 2) {
					++chickenNum;
				}
			}
		}

		// 치킨집의 위치를 저장하는 배열
		chickenPos = new Pos[chickenNum];
		// 고객의 위치를 저장하는 배열
		clientPos = new Pos[clientNum];

		int chickenIdx = 0;
		int clientIdx = 0;
		for (int row = 0; row < N; ++row) {
			for (int col = 0; col < N; ++col) {
				if (map[row][col] == 1) {
					clientPos[clientIdx++] = new Pos(row, col);
				} else if (map[row][col] == 2) {
					chickenPos[chickenIdx++] = new Pos(row, col);
				}
			}
		}

		selected = new int[M];
		ans = Integer.MAX_VALUE;
		combination(0, 0);

		System.out.println(ans);
	}

	private static void combination(int selectIdx, int elementIdx) {
		// 기저조건1
		if (selectIdx == M) {
			// 해당 조합에서의 거리의 합
			int localDistSum = 0;

			// 각 집에서 모든 치킨집까지의 거리 중 최소값을 더한다.
			for (Pos client : clientPos) {
				// 개인에 대한 치킨집까지의 최소거리
				int personalDist = Integer.MAX_VALUE;
				for (int idx = 0; idx < M; ++idx) {
					// 현재 살펴볼 치킨 집
					Pos chicken = chickenPos[selected[idx]];
					// 이전에 계산한 치킨집에 대한 거리와 비교
					personalDist = Math.min(personalDist,
							Math.abs(client.x - chicken.x) + Math.abs(client.y - chicken.y));
				}
				// 도시 치킨거리에 개인 치킨거리 합산
				localDistSum += personalDist;
			}
			// 최소값 선택
			ans = Math.min(ans, localDistSum);
			return;
		}
		// 기저조건2
		if (elementIdx == chickenNum) {
			return;
		}
		// 전처리
		selected[selectIdx] = elementIdx;
		// 선택O
		combination(selectIdx + 1, elementIdx + 1);
		// 선택X
		combination(selectIdx, elementIdx + 1);
	}

	static class Pos {
		int x, y;

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

	}
}

 

---

3. 디버깅

치킨 집의 개수가 최대 13개 밖에 되지 않는 입력을 통해 조합을 통해 구현 방향을 잡았다. 

 

기본적인 조합 코드 중 기저조건에 대해 해당 조합이 유효한 조합(최소 거리를 갖는 치킨집의 조합인가)인지 판단하는 로직이 중요하다.

---

4. 결과