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

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

15686번: 치킨 배달

1. 문제 설명

 

크기가 N*N ( 2 <=N <=50)인 도시가 주어진다.

 

도시는 0 빈칸, 1 집, 2 치킨집으로 구성되어 있다.

 

집과 가장 가까운 치킨집 사이의 거리를 치킨 거리라고 할 때 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

 

* 거리는 맨해튼 거리

 

최대 M(1 <=M <=13) 개의 치킨집만 선택하고 나머지는 폐업시키려고 할 때, 도시의 치킨 거리의 최솟값을 구하는 문제.

 

* M <=치킨집의 개수 <=13

 

2. 풀이

 

N과 M이 작아서 완전 탐색으로 풀 수 있는 문제이다.

 

N이 최대 50이고, 도시에 있을 수 있는 최대 치킨 집의 개수가 13이다.

 

도시의 치킨집 13개를 제외하고 모두 집이 존재한다고 하였을 때 계산해야 하는 경우의 수는

 

2487(집의 개수) * 13C6 (최악의 경우) = 4,267,692

 

충분히 1초 안에 계산 가능하다.

 

나머지 구현은 보통의 브루트 포스 알고리즘처럼 구현하면 된다.

 

도시에 존재하는 치킨집 들 중에서 M개를 선택한 조합을 만들고 각 집에 대한 치킨 거리를 구한 뒤, 도시의 치킨 거리를 구하고 그중 최솟값을 출력하면 된다.

 

문제에서 최대 M개를 선택하라고 했는데 치킨집 M개를 가진 조합을 만드는 이유는 치킨집이 많을수록 도시의 치킨 거리가 작아지기 때문이다..!

 

치킨집이 1개 있는 것보다는 3개 있는 것이 각 집에 대한 치킨 거리가 작을 것이다.

 

처음에 MAX 값을 잘 못 설정해서 틀렸는데, 도시의 치킨 거리의 MAX 값을 200으로 설정했다.

 

치킨 거리 (집 - 치킨 집 거리)의 최댓값은 100이고, 도시의 치킨 거리의 최댓값은 대략 250000이다.

 

치킨 거리의 최댓값은  집이 (0,0) 치킨 집이 (50,50)에 있을 경우 100이 나오게 된다.

 

도시의 치킨 거리의 최댓값은 치킨 거리의 최댓값 * N* N을 통해 대략 250000이 나오게 된다.

 

로직이 맞는 것 같은데 틀리시는 분들은 MAX값을 잘 설정했는지 확인해보자..!

 

참고로 최댓값은 가능한 값의 최댓값이기 때문에 저 값보다 크게 설정해야 한다.

 

 

*로직

- 도시를 입력받는다. 1인 경우 home list에 저장하고 2인 경우 chicken list에 저장한다.

- chicken list에서 치킨집을 선택해나가며 좌표를 choiceIndex에 저장한다.

- 치킨집 M개를 선택한 경우 도시의 치킨 거리를 구한다.

 

3. 코드

import java.awt.*;
import java.io.*;
import java.util.*;

public class Main {

    public static int city_line, chicken_choice_num;
    public static ArrayList<Point> home = new ArrayList<>();
    public static ArrayList<Point> chicken = new ArrayList<>();
    public static Point[] choiceIndex;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        city_line = Integer.parseInt(st.nextToken());
        chicken_choice_num = Integer.parseInt(st.nextToken());

        choiceIndex = new Point[chicken_choice_num];

        for (int x = 0; x < city_line; x++) {
            st = new StringTokenizer(br.readLine());

            // 1-> 집, 2-> 치킨집
            for (int y = 0; y < city_line; y++) {

                int now = Integer.parseInt(st.nextToken());

                if (now == 1) {
                    home.add(new Point(x, y));
                } else if (now == 2) {
                    chicken.add(new Point(x, y));
                }
            }
        }

        System.out.println(chickenChoice(0,0));




    }

    public static int chickenChoice(int idx,int choice_idx) {

        // 치킨 집 선택 완료
        if (choice_idx == chicken_choice_num) {



            return calDistance();
        }


        int ans = 250001;

        for (int x = idx; x < chicken.size(); x++) {
            choiceIndex[choice_idx] = chicken.get(x);
            ans = Math.min(ans, chickenChoice(x + 1, choice_idx + 1));
        }

        return ans;


    }

    public static int calDistance() {
        int homeSize = home.size();

        int sum = 0;

        for (int x = 0; x < homeSize; x++) {
            Point nowHome = home.get(x);

            int minMove = 200;

            for (int y = 0; y < chicken_choice_num; y++) {

                Point nowChicken = choiceIndex[y];

                minMove = Math.min(Math.abs(nowHome.x - nowChicken.x) + Math.abs(nowHome.y - nowChicken.y), minMove);
            }

            sum += minMove;

        }

        return sum;


    }

    static class Point{
        int x, y;

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


}