백준 - 치킨 배달 (15686)

1. 문제

문제 링크

2. 풀이

DFS를 이용해서 폐업시키지 않을 치킨집을 고르는 경우의 수를 모두 만든 다음에
각 경우마다 치킨 거리를 계산해서 최소값을 반환하게 만들면 됩니다.

차근차근 구현해보겠습니다.

계획 1 - 집과 치킨집의 좌표를 각각 리스트에 담습니다.

// 집의 좌표를 담을 리스트
static List<int[]> homes = new ArrayList<>();
// 치킨집의 좌표를 담을 리스트
static List<int[]> chickens = new ArrayList<>();

for (int i = 0; i < N; i++) {
	stk = new StringTokenizer(br.readLine());
			
	for (int j = 0; j < N; j++) {
		int cell = Integer.parseInt(stk.nextToken());
		// 집일 때		
		if (cell == 1) {
			homes.add(new int[] {i + 1, j + 1});
		}
                // 치킨집일 때
		else if (cell == 2) {
			chickens.add(new int[] {i + 1, j + 1});
		}
	}
}

치킨 거리를 계산하려면 집과 치킨집의 좌표를 알아야합니다.

계획 2 - DFS로 치킨집을 고르는 모든 경우의 수를 만듭니다.

for (int i = startIndex; i < chickens.size(); i++) {
	picked.add(chickens.get(i));
	ret = Math.min(ret,  min(m - 1, i + 1, picked));
	picked.pop();
}

여기서 picked변수는 stack자료구조로서 우리가 뽑은 치킨집의 좌표들이 들어있습니다.
재귀함수가 동작하는 방식은 stack자료구조와 동일하기 때문에 문제를 더 쉽게 해결할 수 있습니다.

startIndex는 이전에 뽑은 치킨집의 다음 치킨집부터 뽑아주도록 설정하기 위한 변수입니다.

스타트와 링크 포스팅에서도 설명했듯이 재귀 함수가 탐색할 때
이런 트리 모양으로 탐색합니다.
[1, 2, 3, 4] 처럼 4개의 치킨집 중에서 2개의 치킨집을 뽑을 때
[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]가 경우의 수로 뽑히게 됩니다.

계획 3 - 치킨 거리를 계산합니다

int sum = 0;
// 집의 좌표들	
for (int[] home: homes) {
	int dist = INF;
	// 치킨집의 좌표들	
	for (int[] pick: picked) {
          	// 거리 공식을 이용해 가장 가까운 거리를 구합니다.
		dist = Math.min(dist, Math.abs(home[0] - pick[0]) + Math.abs(home[1] - pick[1]));
	}
				
	sum += dist;
}
			
return sum;

집들에 대해서 뽑힌 치킨집들과 일일이 다 비교해서 최소값만 취해서 더합니다.

총 시간 복잡도는
치킨집의 개수를 C
집의 개수를 H라고 했을 때
치킨집을 뽑는 모든 경우의 수는 H! / ((H - M)! X M!) 개가 나오고
각 경우의 수마다 치킨 거리를 계산할 때 O(H X C)의 시간이 걸리므로
총 시간 복잡도는 ((H! X H X C) / ((H - M)! X M!) 가 됩니다.

전체 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static final int INF = 987654321;
	static List<int[]> homes = new ArrayList<>();
	static List<int[]> chickens = new ArrayList<>();
	
	static int min(int m, int startIndex, Stack<int[]> picked) {
		// 기저 사례 - 치킨집을 M개 뽑았을 때
		if (m == 0) {
			// 계획 3 - 치킨 거리를 계산합니다
			int sum = 0;
			
			for (int[] home: homes) {
				int dist = INF;
				
				for (int[] pick: picked) {
					dist = Math.min(dist, Math.abs(home[0] - pick[0]) + Math.abs(home[1] - pick[1]));
				}
				
				sum += dist;
			}
			
			return sum;
		}
		
		int ret = INF;
		
		// 계획 2 - DFS로 치킨집을 고르는 모든 경우의 수를 만듭니다.
		for (int i = startIndex; i < chickens.size(); i++) {
			picked.add(chickens.get(i));
			ret = Math.min(ret,  min(m - 1, i + 1, picked));
			picked.pop();
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		StringTokenizer stk = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stk.nextToken());
		int M = Integer.parseInt(stk.nextToken());
		
		// 계획 1 - 집과 치킨집의 좌표를 각각 리스트에 담습니다.
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < N; j++) {
				int cell = Integer.parseInt(stk.nextToken());
				
				if (cell == 1) {
					homes.add(new int[] {i + 1, j + 1});
				}
				else if (cell == 2) {
					chickens.add(new int[] {i + 1, j + 1});
				}
			}
		}
		
		bw.write(min(M, 0, new Stack<>()) + "");
		bw.close();
	}
}