백준 - 15686 치킨 배달(Java)

조합(백트랙킹) 문제입니다.

 

N*N의 맵에서 M개 이상의 치킨 집이 주어집니다.

M개 이상의 치킨 집을 M개의 치킨 집만을 만들어 각 집에서의 최소 거리를 구해야 하는 문제입니다.

즉, M개 이상의 치킨 집을 조합으로 M개로 만들어 거리를 구하는 완전탐색 문제인 것입니다.

 

[구현 코드]

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    private static int n, m;
    private static List<int[]> chickens, homes;
    private static List<int[][]> combis; // 치킨 집 조합

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());

        chickens = new ArrayList<>();
        homes = new ArrayList<>();
        combis = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                int homeOrChicken = Integer.parseInt(stz.nextToken());

                // 집
                if (homeOrChicken == 1) {
                    homes.add(new int[]{i, j});
                }

                // 치킨
                else if (homeOrChicken == 2) {
                    chickens.add(new int[]{i, j});
                }
            }
        }

        // 치킨 조합
        int r = m;
        chickenCombination(chickens.size(), r, 0, new boolean[chickens.size()]);

        int answer = Integer.MAX_VALUE;

        for (int[][] combi : combis) {
            int homeToChickenTotal = 0;

            // 집에서 최소 치킨 거리를 구함
            for (int[] home : homes) {
                int min = Integer.MAX_VALUE;

                for (int[] com : combi) {
                    int x = Math.abs(home[0] - com[0]);
                    int y = Math.abs(home[1] - com[1]);

                    min = Math.min(min, (x + y));
                }
                homeToChickenTotal += min;
            }
            answer = Math.min(answer, homeToChickenTotal);
        }

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }

    private static void chickenCombination(int n, int r, int depth, boolean[] visited) {
        if (r == 0) {
            int cnt = 0;
            int[][] tmp = new int[m][2];
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    tmp[cnt++] = chickens.get(i);
                }
            }
            combis.add(tmp);
            return;
        }

        if (depth >= n) return;

        // 현재 치킨을 조합에 포함
        visited[depth] = true;
        chickenCombination(n, r - 1, depth + 1, visited);

        // 현재 치킨을 조랍에 포함하지 않음
        visited[depth] = false;
        chickenCombination(n, r, depth + 1, visited);
    }
}