BOJ 15686 [치킨 배달]

BOJ 치킨 배달 : https://www.acmicpc.net/problem/15686

안녕하세요. 이번 문제는 백준 온라인 저지의 [치킨 배달] 입니다.

우선, 저의 문제 해결방법에서 가장 중요한 포인트는 바로, "모든 치킨집 중에서 M개를 뽑기" 입니다.

1. DFS를 통해 치킨집을 M개 고른다. (boolean 배열을 통해 선택할지 안할지 체크)

2. M만큼의 치킨집을 모두 고르면, 각 집에서의 치킨거리를 구한다.

import java.util.*;
public class Main {
    public static int result = 999999999;
    public static int N, M;
    public static int[][] Map;
    public static boolean[] choice = new boolean[13];
    public static ArrayList<int[]> Chicken = new ArrayList<int[]>();
    public static void DFS(int cnt, int index) {
        if(cnt == M) {
            int temp_res = 0;
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    if(Map[i][j] == 1) {
                        int dist = 99999999;
                        for(int k = 0; k < Chicken.size(); k++) {
                            if(choice[k]) {
                                if(dist > Math.abs(i - Chicken.get(k)[0]) + Math.abs(j - Chicken.get(k)[1]))
                                    dist = Math.abs(i - Chicken.get(k)[0]) + Math.abs(j - Chicken.get(k)[1]);
                            }
                        }
                        temp_res += dist;
                    }
                }
            }
            if(result > temp_res)
                result = temp_res;
            return;
        }
        for(int i = index + 1; i < Chicken.size(); i++) {
            choice[i] = true;
            DFS(cnt + 1, i);
            choice[i] = false;
        }
    }
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       N = sc.nextInt();
       M = sc.nextInt();
       Map = new int[N][N];
       for(int i = 0; i < N; i++) {
           for(int j = 0; j < N; j++) {
               Map[i][j] = sc.nextInt();
               if(Map[i][j] == 2) {
                   int[] c = new int[2];
                   c[0] = i;
                   c[1] = j;
                   Chicken.add(c);
                }
           }
       }
       DFS(0, -1);
       System.out.println(result);
    }
}