[백준 15686번] 치킨 배달

문제 링크: 15686번 치킨 배달

https://www.acmicpc.net/problem/15686

 

치킨 집 중 m개를 뽑고, 각 집에서 가장 가까운 치킨집까지의 거리를 구한 후 이를 더해서 치킨 거리를 구한다. 이 치킨 거리가 최소일 때가 정답이다.

2차원 배열을 계속해서 이용하기보다는 집과 치킨집들의 좌표를 따로 저장해두고 이 두 배열만을 이용하는 것이 빠를 듯하다.

 

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

class Pos {
    int row;
    int col;

    Pos(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class Main {
    static int n;
    static int m;
    static int minChickenDist = Integer.MAX_VALUE;
    static ArrayList<Pos> house = new ArrayList<>();
    static ArrayList<Pos> chicken = new ArrayList<>();
    static int[][] map;

    static int getChickenDist(boolean[] exist) {
        Pos[] remainChicken = new Pos[m];
        int idx = 0;
        for (int i=0; i<exist.length; i++)
            if (exist[i])
                remainChicken[idx++] = chicken.get(i);

        int chickenDist = 0;

        for (Pos pos : house) {
            int chickenDistOneHouse = Integer.MAX_VALUE;
            for (int j=0; j<m; j++) {
                int temp = Math.abs(remainChicken[j].row - pos.row) +
                        Math.abs(remainChicken[j].col - pos.col);
                if (temp < chickenDistOneHouse)
                    chickenDistOneHouse = temp;
            }
            chickenDist += chickenDistOneHouse;
        }

        return chickenDist;
    }

    static void makeComb(boolean[] exist, int num, int idx) {
        if (num == m) {
            // m개 치킨집
            int chickenDist = getChickenDist(exist);
            if (chickenDist < minChickenDist)
                minChickenDist = chickenDist;
            return;
        }
        if (idx == exist.length) {
            return;
        }

        exist[idx] = true;
        makeComb(exist, num+1, idx+1);
        exist[idx] = false;
        makeComb(exist, num, idx+1);
    }

    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());
        map = new int[n][n];

        for (int i=0; i<n; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j=0; j<n; j++) {
                if (map[i][j] == 1) house.add(new Pos(i, j));
                if (map[i][j] == 2) chicken.add(new Pos(i, j));
            }
        }

        boolean[] exist = new boolean[chicken.size()];
        int num = 0;
        int idx = 0;
        makeComb(exist, num, idx);
        System.out.println(minChickenDist);
    }
}