[백준 15686] 치킨 배달

 

백트래킹으로 모든 집에 대해 치킨거리를 구해야 한다.

 

배열을 쓰는 것보다는 집, 치킨집을 리스트에 담아서 구현하는게 빨라서 이중루프로 치킨거리를 구하게 했다.

 

치킨집 중에 M개 만큼의 치킨집을 골라 스택에 담아 백트래킹으로 탐색했고,

리스트를 쓰든 벡터를 쓰던 상관은 없다.

 

이 문제 역시 중복없는 완전탐색이 핵심이다.

 

public class Main {
    
    static int n;
    static int m;
    static ArrayList<Pair> h = new ArrayList<Pair>();
    static ArrayList<Pair> ch = new ArrayList<Pair>();
    static Stack<Pair> choice = new Stack<Pair>();
    static int ans = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        for(int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++) {
                int k = Integer.parseInt(st.nextToken());
                if(k == 1) h.add(new Pair(i, j));
                if(k == 2) ch.add(new Pair(i, j));
            }
        }
        
        setChicken(0, 0);
        System.out.println(ans);
    }
    
    public static void setChicken(int idx, int cnt) {
        if(cnt == m) {
            distance();
            return;
        }
        
        for(int i=idx; i<ch.size(); i++) {
            choice.push(ch.get(i));
            setChicken(i+1, cnt+1);
            choice.pop();
        }
    }
    
    public static void distance() {
        int sum = 0;
        for(int i=0; i<h.size(); i++) {
            int min = Integer.MAX_VALUE;
            for(int j=0; j<choice.size(); j++) {
                int diff = Math.abs(h.get(i).r - choice.get(j).r) + Math.abs(h.get(i).c - choice.get(j).c);
                min = Math.min(min, diff);
            }
            sum += min;
            if(sum > ans) return;
        }
        ans = Math.min(ans, sum);
    }
    
    static class Pair {
        int r;
        int c;
        
        Pair(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}