[JAVA] 백준 15686 - 치킨배달

 

 

 

치킨집이 최대 13개고, 각 집에대한 치킨거리는 O(1)로 구할수있기때문에 

브루트포스로 한다고 했을떄 13Cn * 2N이 최대이다.
이경우 시간이 넉넉하기떄문에

브루트포스로 일일히 치킨집을 조합해서 다 경우의수를 따져봐도 시간초과가 나지않는다.

 

그러나 아이디어는 다 생각했는데 치킨집 조합을 어떻게 브루트포스로 조합하지?

멍청하게 이걸 몰라서 문제를 못풀어 답을 봤다.

 

dfs + 백트래킹으로 조합을 따질 수 있었다.

이런 풀이는 많이 나오니까 어느정도 구조를 외우고 나중에 또 비슷한 문제풀이가나올때 바로 떠올릴수있도록 반복해야겠다고 생각했다.

 

 

import javax.sound.sampled.Line;

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class Main {
    public static int N;
    public static int M;
    static ArrayList<Point> chicken = new ArrayList<>();
    static ArrayList<Point> house = new ArrayList<>();
    static HashSet<Point> chickenSet = new HashSet<>();
    static boolean[] visited;
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lines = br.readLine().split(" ");
        N = Integer.parseInt(lines[0]);
        M = Integer.parseInt(lines[1]);
        visited = new boolean[M];
        for (int i = 0; i < N; i++) {
            lines = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                int num = Integer.parseInt(lines[j]);
                if (num == 1) house.add(new Point(i, j));
                else if (num == 2) chicken.add(new Point(i, j));
            }
        }
        dfs(0,0);
//        System.out.println(house);
        System.out.println(ans);


    }

    public static void dfs(int depth, int count) {
        if (count == M) {
            //최솟값 계산
            int sum = 0;
            for(int i = 0 ; i < house.size(); i++) {
                int min = Integer.MAX_VALUE;
                Point housePoint = house.get(i);
                Iterator<Point> it = chickenSet.iterator();
                while (it.hasNext()) {
                    Point chickenPoint = it.next();
                    min = Math.min(min, Math.abs(chickenPoint.x - housePoint.x) + Math.abs(chickenPoint.y - housePoint.y));
                }
                sum += min;
//                System.out.println("house" + house.get(i) + "의 치킨거리 : " + min);
            }
//            System.out.println("현재 치킨집 리스트 : " + chickenSet );
//            System.out.println("sum : " + sum);
            ans = Math.min(ans, sum);
        } else {
            for (int i = depth; i < chicken.size(); i++) {
                chickenSet.add(chicken.get(i));
                dfs(i + 1, count + 1);
                chickenSet.remove(chicken.get(i));
            }
        }

    }
}

class Point {
    int x;
    int y;

    public Point() {
    }

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public String toString() {
        return "(" + x + ", " + y + ")";
    }
}