[백준] Q15686 치킨 배달 JAVA

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

15686번: 치킨 배달

 

1. 문제의 이해 및 유형

완전탐색 (조합), 구현

 

"치킨 거리" 집과 가장 가까운 치킨 집 사이의 거리.

구하고자 하는 것이 "도시의 치킨 거리" : 도시에 위치한 집들의 치킨거리 합

도시의 치킨거리가 가장 작도록 골랐을 때 치킨거리의 최소값 구하기.

 

치킨 집 개수인 M이  $1<= N <= 13$개로, 가장 많은 집인 13개에서 가장 큰 값을 구한다면

13C6일 때이고 이 때 1716 가지 경우의 수 밖에 없기 떄문에 완전탐색이라고 생각했다.

 

2. 문제 접근 방식

위와 동일하다.

다만, 자료 정리에 있어서 치킨 거리 계산에는 치킨집의 좌표와 도시에 있는 집의 좌표만 있으면 되기 때문에

list를 통해 자료를 잘 정리해두고 필요에 따라 값만 계산하면된다.

 

/*
2021.12.19
문제번호 : Q15686 
이름 및 난이도 : 치킨 배달 Gold V
문제이해 
-----------------
N*N 도시. 빈칸, 치킨집, 집 
r,c 는 1부터 시작
"치킨거리" >> 집과 가장 가까운 치킨집 사이의 거리.
"도시의 치킨거리" >> 모든 집의 치킨 거리 합
|r1-r2| + |c1-c2|
0 빈칸 1 집 2 치킨집
최대 M개 (수익을 많이 낼 수 있는)
치킨 거리가 가장 작게 .

접근 방법 :
모든 집으로부터 치킨 집까지의 거리를 다 더하는 치킨거리가 총합이 된다.
한 집에서 가장 가깝다고 해서 다른 집도 가까운 상황이 아님.
할 수 있는 방법은 여러가지가 있을 것 같다.
 1. 치킨집 마다 치킨거리를 다 구해서 sorting시킨다음.
    가장 긴 치킨거리를 가지는 치킨 집 부터 제거하여 M개를 만드는 방법.(X)
    잘못된 생각임.
 2. 치킨집 개수가 최대 13개 이고 13에서 가장 큰 조합의 개수는
    13C6 = 1716
    
 조합 마다 하는 방법
    >조합마다 해보는 방법은 같은 치킨집에서의 거리를 구한다.
제한 조건 : 
N 50 M 13 치킨집 개수 <= Min(M,13)

## 중복 허용 X 오름차순 
## 참조 https://www.acmicpc.net/source/32167915
*/

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

public class Main {
    static int N;
    static int M;
    static ArrayList<Point> house;
    static ArrayList<Point> chicken;
    static boolean[] possible;
    static int ans;

    public static void main(String[] args) throws IOException {
        input();
        solution();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        house = new ArrayList<Point>();
        chicken = new ArrayList<Point>();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int option = Integer.parseInt(st.nextToken());
                if (option == 1) {
                    house.add(new Point(i, j));
                } else if (option == 2) {
                    chicken.add(new Point(i, j));
                }
            }
        }
        possible = new boolean[chicken.size()];
    }

    public static void solution() {
        ans = Integer.MAX_VALUE;
        // M개를 골랐을 때
        selectChickenHouse(0, 0);
        System.out.println(ans);
    }


	//조합
    public static void selectChickenHouse(int depth, int idx) {
        if (depth == M) {
            int cityDist = 0;
            for (Point h : house) {
                int chickenDist = Integer.MAX_VALUE;
                for (int i = 0; i < chicken.size(); i++) {
                    if (!possible[i])
                        continue;
                    Point c = chicken.get(i);
                    chickenDist = Math.min(chickenDist, Math.abs(h.x - c.x) + Math.abs(h.y - c.y));
                }
                cityDist += chickenDist;
            }
            ans = Math.min(ans, cityDist);
            return;
        }
        if (chicken.size() - idx < M - depth)
            return;
        for (int i = idx; i < chicken.size(); i++) {
            if (!possible[i]) {
                possible[i] = true;
                selectChickenHouse(depth + 1, i + 1);
                possible[i] = false;
            }
        }

    }

    static class Point {
        int x, y;

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

    }

}

3. 문제점

이 문제를 작성하고 싶었던 건 사실 개인적으로 '백준 - 연구소https://www.acmicpc.net/problem/14502' 를 처음 풀 때 너무 감명받아서 비슷한 느낌의 문제를 보고 다시 한번 생각해보지 않고 작성했었기 때문에 조심하기 위해서...