[Algorithm / Java] 백준 15686번 치킨 배달

key word : 백트랙킹, BackTracking

문제

크기가 N * N인 도시에 M개 이상의 치킨집이 존재할 때, 수익을 많이 낼 수 있는 치킨집을 M개 고르고, 그때의 치킨 거리(집과 치킨집 사이의 거리의 총 합)를 구하는 문제이다. N과 M, 도시 내 집과 치킨집의 위치가 입력으로 주어진다.

처음에는 문제를 잘못 이해해서 치킨집이 M개밖에 없고, 그 상태에서 그냥 치킨 거리만 구하는 문제라고 생각했다. 그래서 BFS를 이용해서 구현해봤는데, 예제를 보다보니 M과 지도 내 치킨집의 개수가 꼭 일치하지는 않는다는 것을 알게 됐다.

아이디어

M과 치킨집의 개수가 같을 경우에 치킨 거리를 구하는 일은 매우 쉽다. BFS로 구할수도 있고, 집과 치킨집의 좌표를 각각 담고있는 리스트를 이용해 min 값을 찾아낼 수도 있다. 아무래도 후자가 훨씬 간편하고 시간도 적게 걸릴 것이다.

그렇다면 M과 치킨집의 개수가 다를 때엔 어떻게 치킨 거리를 구할 수 있을까? 일단 여러 치킨집 중에 M개만 고를 수 있어야하고, M개를 고른 이후에 각각의 조합에 대해 치킨 거리를 구해야 한다. 여러개의 수 중 M개의 조합을 구하는 것은 백트랙킹으로 구할 수 있고, 그 이후 치킨 거리를 구하는 것은 위에서 언급한 것과 같은 방식으로 구할 수 있다.

백트랙킹으로 M개의 조합을 리스트로 만드는 함수와 특정 조합에 대한 치킨 거리를 구하는 함수를 따로 구현했는데, 다른 사람들의 풀이를 참고해보니 하나의 메소드로 구현한 경우가 많았다. 나중에 다시 풀어볼 때에는 그 방식으로도 구현해봐야겠다.

구현

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

public class ChickenDelivery {
	public static int N, M, h = 0, c = 0;
	public static int[] arr;
	public static Integer[][] house, chicken;
	public static ArrayList<Integer[][]> chickenList = new ArrayList<>();

	public static void init() throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] s = br.readLine().split(" ");
		N= Integer.parseInt(s[0]);
		M= Integer.parseInt(s[1]);

		house = new Integer[2 * N][2];
		chicken = new Integer[13][2];
		arr = new int[M];

		for(int i=0; i<N; i++) {
			s = br.readLine().split(" ");
			for(int j=0; j<N; j++) {
				int k = Integer.parseInt(s[j]);
				if(k == 1) {
					house[h++] = new Integer[] {i, j};
				}
				if(k == 2) {
					chicken[c++] = new Integer[] {i, j};
				}
			}
		}

		br.close();
	}

	public static int distance(Integer[][] store) {
		int cnt = 0;

		for(int i=0; i<h; i++) {
			int min = N * N;
			for(int j=0; j<M; j++) {
				int d = Math.abs(house[i][0] - store[j][0]) + Math.abs(house[i][1] - store[j][1]);
				min = min > d ? d : min;
			}
			cnt += min;
		}

		return cnt;
	}

	public static void recursion(int k, int at) {
		if(k == M) {
			Integer[][] nArr = new Integer[M][2];
			for(int i=0; i<M; i++) {
				nArr[i] = chicken[arr[i]];
			}
			chickenList.add(nArr);
			return;
		}

		for(int i=at; i<c; i++) {
			arr[k] = i;
			recursion(k + 1, i + 1);
		}
	}

	public static void main(String[] args) throws IOException{
		init();
		if(M == c) {
			System.out.println(distance(chicken));
		}else {
			recursion(0, 0);
			int min = Integer.MAX_VALUE;
			int m;

			for(Integer[][] list : chickenList) {
				m = distance(list);
				min = min > m ? m : min;
			}

			System.out.println(min);
		}

	}
}