[백트래킹] 15686. 치킨 배달

[BOJ] 15686. 치킨 배달

📌 풀이 과정

백트래킹 + 조합 문제

1. 집의 위치와 치킨집 위치를 ArrayList<int[]> 에 따로 저장했다.

2. 도시에 있는 치킨집 중에서 최대 M개를 조합으로 선택한다.

3. 모든 집에 대해 M개의 치킨집 중 최단 거리를 계산한다.

✨ 제출 코드

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

public class Main {

	static int N, M, minChickenStreet = Integer.MAX_VALUE;
	static int[][] map;
	static ArrayList<int[]> chicken = new ArrayList<>();
	static ArrayList<int[]> home = new ArrayList<>();
	static ArrayList<int[]> choice = new ArrayList<>();
	
	
	public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 맵 크기
        M = Integer.parseInt(st.nextToken()); // M < 치킨집 <= 13
        map = new int[N][N];
        
        
        for(int i = 0; i < N; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j = 0; j < N; j++) {
        		map[i][j] = Integer.parseInt(st.nextToken());
        		if(map[i][j] == 1) home.add(new int[]{i, j}); // 집인 경우
        		else if(map[i][j] == 2) chicken.add(new int[]{i, j}); // 치킨집인 경우
        	}
        }
        
        pickChicken(0, 0);
        System.out.println(minChickenStreet);
        
	}
	
	static void pickChicken(int depth, int start) {
		if(depth == M) { // 선택한 치킨집이 M개인 경우
			int sum = 0;
			for(int[] h : home) { // 모든 집과 선택한 M개의 치킨집 간의 최소 거리 구하기
				int min = Integer.MAX_VALUE;
				for(int[] c : choice) {
					int dis = Math.abs(c[0] - h[0]) + Math.abs(c[1] - h[1]);
					min = Math.min(dis, min);
				}
				sum += min;
			}
			minChickenStreet = Math.min(sum, minChickenStreet);
			return;
		}
		
		for(int i = start; i < chicken.size(); i++) {
			choice.add(chicken.get(i));
			pickChicken(depth + 1, i + 1);
			choice.remove(choice.size() - 1);
		}
	}
	
	

}