백준 15686번 - 치킨 배달

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

15686번: 치킨 배달

문제 풀이

1. 최대 M 개이므로 살아남는 치킨 집이 한 점포부터 M개의 점포까지 모든 경우의 수가 생긴다. 따라서 이 경우들을 모두 따져주어야 도시의 치킨 거리의 최소값을 계산할 수 있을 것이다.

 따라서 K개의 치킨 집이 있다면 그 중, 1~M개의 치킨 집을 선택하여야 한다. 앞서 비트 마스크에 대한 글을 올렸으므로, 이번 문제도 비트 마스크를 이용하여 풀어보았다. 살짝 다른 점이 있다면 1~M개를 선택해야 하므로 0을 걸러주어야 한다.

 

2. 처음엔 치킨 집을 우선시 하여 치킨 집의 반복문을 앞서 작성하였는데 이렇게 작성시 일반 집의 반복문이 안으로 들어가 살아있는 모든 치킨 집에 대한 각 일반 집의 치킨 거리의 최소값을 저장해두기가 애매해진다. 배열을 사용할 수도 있지만 일반 집의 반복문을 앞서 작성하면, 한 집에 대해서 다음번 치킨 집 반복문에서 모든 치킨 거리를 구할 수 있기 때문에 이경우가 좀 더 효율적이다.

 

3. 위에서 구한 각 집의 치킨 거리의 최소값을 모두 더하여 이를 최종 변수와 비교하면서 최소값을 도출해낸다.

 

 

import java.util.ArrayList;
import java.util.Scanner;

class Pair {
    int x; 
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class BOJ15686 {
    static int n;
    static int m;
    static int[][] inputAry;
    static ArrayList<Pair> storeList;
    static ArrayList<Pair> personList;
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        inputAry = new int[n][n];
        storeList = new ArrayList<Pair>();
        personList = new ArrayList<Pair>();
        ArrayList<Pair> answerList = new ArrayList<Pair>();
	    
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                inputAry[i][j] = sc.nextInt();
                if(inputAry[i][j] == 2) {
                    storeList.add(new Pair(i,j));
                } else if(inputAry[i][j] == 1) {
                    personList.add(new Pair(i,j));
                }
            }
        }
        System.out.println(storeList.size());
        boolean[] check = new boolean[storeList.size()];
	    
        dfs(0,0, answerList, check);
        System.out.println(answer);
    }
    public static void dfs(int start, int depth, ArrayList<Pair> answerList, boolean[] check) {
        if(depth == m) {
            int sum = calAnswer(answerList);
            answer = Math.min(answer, sum);
            return;
        }
        for(int i = start; i < storeList.size(); i++) {
            if(check[i])
                continue;
            check[i] = true;
            answerList.add(storeList.get(i));
            dfs(i+1, depth+1, answerList, check);
            answerList.remove(answerList.size()-1);
            check[i] = false;
        }
    }
	public static int calAnswer(ArrayList<Pair> answerList) {
        int sum = 0;
        for(int i = 0; i < personList.size(); i++) {
            Pair p1 = personList.get(i);
            int len = Integer.MAX_VALUE;
            for(int j = 0; j < answerList.size(); j++) {
                Pair p2 = answerList.get(j);
                int temp = Math.abs(p1.x-p2.x) + Math.abs(p1.y-p2.y);
                len = Math.min(len, temp);
            }
            sum += len;
        }
        return sum;
    }
}