[JAVA] 백준 15686번 : 치킨 배달

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

15686번: 치킨 배달

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M, answer = Integer.MAX_VALUE;
    static int[][] distance;
    static int[] chickenM;
    static List<Pos> chickenRest = new ArrayList<>();
    static List<Pos> house = new ArrayList<>();

    private static class Pos {
        int x;
        int y;

        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        chickenM = new int[M];
        for (int i = 0; i < N; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                if(line[j].equals("1"))
                    house.add(new Pos(i, j));
                else if(line[j].equals("2"))
                    chickenRest.add(new Pos(i, j));
            }
        }
        distance = new int[house.size()][chickenRest.size()]; //row=집번호, col=치킨집 번호
        //각 집 <-> 치킨집 사이 거리 저장
        for (int i = 0; i < distance.length; i++) {
            Pos nh = house.get(i);
            for (int j = 0; j < chickenRest.size(); j++) {
                Pos cr = chickenRest.get(j);
                distance[i][j] = Math.abs(nh.x - cr.x) + Math.abs(nh.y - cr.y);
            }
        }
        searchMin(0, 0);
        System.out.println(answer);
    }

    private static void searchMin(int cIdx, int cnt) {
        if (cnt == M){
            int tmp = getDistSum();
            answer = Math.min(answer, tmp);
            return;
        }
        for (int i = cIdx; i < chickenRest.size(); i++) {
            chickenM[cnt] = i;
            searchMin(i+1, cnt + 1);
        }
    }

    private static int getDistSum() {//각 집마다 M개 후보 치킨집 중 최소 거리 계산해 더함
        int sum = 0;
        for (int i = 0; i < house.size(); i++) {
            int tmp = Integer.MAX_VALUE;
            for (int j = 0; j < chickenM.length; j++) {
                tmp = Math.min(tmp, distance[i][chickenM[j]]);
            }
            sum += tmp;
        }
        return sum;
    }
}

💡 브루트포스, 구현

풀이

• 처음에는 치킨집 객체를 따로 만들어서 리스트에 저장한 후, 치킨집마다 각 집까지의 치킨거리의 총 합을 객체에 저장함 -> 거리 합 기준 오름차순으로 정렬한 뒤 M개만 뽑아 각 거리를 구하고 그 중 최솟값의 합 구함 
• 문제점 >> 거리 합이 같은 객체여도, 막상 집까지의 거리는 다른 양상일 가능성이 큼. 즉, 가게를 어떻게 조합하는지에 따라 최솟값의 합이 다르게 나올 수 있음
• 브루트포스 방식을 사용해 다 구하는 방법으로 생각해야 할듯

---

1. 치킨집 위치, 일반 집 위치를 객체로 만들어 각각 리스트에 저장한다.
2. 각 치킨집 - 집까지의 거리를 2차원 배열로 저장한다 [치킨 집 번호][일반 집 번호]
3. M개의 치킨집을 뽑는 모든 경우의 수를 시도해 봄 -> M개를 뽑았을 때, 최솟값을 갱신해준다.