백준 15686 - 치킨배달

백트래킹 -> DFS 조합

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    static int N;
    static int M;
    static int[][] map;
    static int house = 0;
    static int[] pick = new int[13];
    static int[][] tempMap;
    static LinkedList<Pair> list = new LinkedList<>();
    static int sum =0;
    static int result = 9999;

    public static void main(String[] args){

        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        M = scanner.nextInt();

        map = new int[N+1][N+1];
        tempMap = new int[N+1][N+1];

        for(int r=1; r<N+1; r++){
            for(int c=1; c<N+1; c++){
                map[r][c] = scanner.nextInt();
                if(map[r][c] == 2){
                    house++;
                    Pair pair = new Pair(r,c);
                    list.add(pair);
                }
            }
        }


        comb(0,0);
        System.out.println(result);


    }

    static void comb(int start, int depth){

        if(depth == M){
            finalMap();
            result = Math.min(result, distance());
            return;
        }

        for(int i=start; i<house; i++){

            pick[i] = 1;
            comb(i+1, depth+1);
            pick[i] = 0;
        }

    }

    static void finalMap(){

        for(int r=1; r<N+1; r++){
            for(int c=1; c<N+1; c++){
                tempMap[r][c] = map[r][c];
            }
        }

        for(int i=0; i<pick.length; i++){
            if(pick[i] == 1){
                Pair pair = list.get(i);
                int r = pair.x;
                int c = pair.y;
                tempMap[r][c] = 3;
            }
        }

    }

    static class Pair{
        int x;
        int y;

        Pair(int r, int c){
            this.x = r;
            this.y = c;
        }


    }

    static int distance(){

        int minDistance = 9999;
        sum =0 ;
        for(int r=1; r<N+1; r++){
            for(int c=1; c<N+1; c++){
                if(tempMap[r][c] == 1){
                    for(int a=1; a<N+1; a++){
                        for(int b=1; b<N+1; b++){
                            if(tempMap[a][b] == 3){
                                int distance = Math.abs(a-r) + Math.abs(b-c);
                                if(minDistance > distance)
                                    minDistance = distance;
                            }
                        }
                    }
                    sum += minDistance;
                    minDistance=9999;
                }
            }
        }

        return sum;

    }


}