(알고리즘) boj - 치킨배달 (15686)

www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

풀이과정

문제 설명

• 각각의 치킨집의 위치와 도시의 위치가 주어진다.
• 치킨집의 개수가 주어진다. (치킨집의 개수 = 뽑아야 할 치킨집 개수)
• 도시를 기준으로 치킨집 간의 최소 거리를 구한 다음에 최소 거리를 합해서 최소한의 도시의 치킨 거리를 구한다.

 

문제에서 가장 중요한 것은 치킨집을 뽑는 것이다.

모든 경우를 뽑을 필요는 없기 때문에 순서가 있는 조합을 사용하는 게 핵심이다.

jwdeveloper.tistory.com/272?category=847363

(알고리즘) N과 M (2) - 조합

    // 조합생성
    private static void combination(int index, int depth) {

        if (depth == m) {
            List<Where> result = new ArrayList<Where>();
            for (int i = 0; i < m; i++) {
                result.add(chicken.get(arr[i]));
            }
            // 계산시작
            calculate(result);

            return;
        }

        for (int i = index; i < chicken.size(); i++) {
            arr[depth] = i;
            combination(i + 1, depth + 1);
        }
    }

 

이 문제를 풀 때 조합을 구하는 데는 이상이 없었지만 문제를 제대로 파악하지 못하여 기준을 잘못 세워 헤맸다.

도시를 기준으로 뽑은 치킨집 과의 최소거리를 구해야 하는데

반대로 생각하였다.

 

문제를 잘 읽자!

---

소스코드

public class Chicken {
    private static int n;
    private static int m;
    private static int[][] map;
    private static List<Where> home;
    private static List<Where> chicken;
    private static int[] arr;
    private static int calculateResult = Integer.MAX_VALUE;

    public static void main(String[] args) {
        init();

        combination(0, 0);

        System.out.println(calculateResult);
    }

    // 조합생성
    private static void combination(int index, int depth) {

        if (depth == m) {
            List<Where> result = new ArrayList<Where>();
            for (int i = 0; i < m; i++) {
                result.add(chicken.get(arr[i]));
            }
            // 계산시작
            calculate(result);

            return;
        }

        for (int i = index; i < chicken.size(); i++) {
            arr[depth] = i;
            combination(i + 1, depth + 1);
        }
    }

    private static void calculate(List<Where> result) {
        int gogo = 0;
        for (int i = 0; i < home.size(); i++) {
            int homeX = home.get(i).getX();
            int homeY = home.get(i).getY();
            int homeChickenDistance = Integer.MAX_VALUE;

            for (int j = 0; j <result.size(); j++) {
                int chickenX = result.get(j).getX();
                int chickenY = result.get(j).getY();

                int absCalculate = absCalculate(chickenX, chickenY, homeX, homeY);
                homeChickenDistance = Math.min(absCalculate, homeChickenDistance);
            }
            gogo += homeChickenDistance;
        }
        calculateResult = Math.min(gogo, calculateResult);

    }

    private static int absCalculate(int chickenX, int chickenY, int homeX, int homeY) {
        return Math.abs(homeX - chickenX) + Math.abs(homeY - chickenY);
    }

    private static void init() {
        Scanner scanner =  new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        arr = new int[m];
        map = new int[n][n];

        home = new ArrayList<>();
        chicken = new ArrayList<>();

        scanner.nextLine();

        for (int i = 0; i < n; i++) {
            String[] str = scanner.nextLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(str[j]);
                // 집 위치 저장
                if (map[i][j] == 1) {
                    home.add(new Where(i, j));
                }
                // 치킨집 위치 저장
                if (map[i][j] == 2) {
                    chicken.add(new Where(i, j));
                }
            }
        }
    }
}
class Where {
    private final int x;
    private final int y;

    public Where(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}