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

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

 

예전에 풀어봤던 문제인데 다시 풀어보도록 하자.

 

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

public class Main {
    public static int N, M, min = Integer.MAX_VALUE, hsize, csize;
    public static List<int[]> houses, chickens;
    public static int[] alive;
    public static int[][] dis;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        houses = new ArrayList<>();
        chickens = new ArrayList<>();

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                int a = Integer.parseInt(st.nextToken());
                if(a == 1) houses.add(new int[] {i, j});
                else if(a == 2) chickens.add(new int[] {i, j});
            }
        }

        // 집과 치킨집과의 거리 계산해두기
        hsize = houses.size();
        csize = chickens.size();
        dis = new int[hsize][csize];
        int i = 0, j = 0;
        for(int[] house : houses){
            for(int[] chicken : chickens){
                dis[i][j++] = Math.abs(house[0] - chicken[0]) + Math.abs(house[1] - chicken[1]);
            }
            i++;
            j = 0;
        }

        // 치킨집 조합 선정
        alive = new int[M];
        dfs(0,0);

        System.out.println(min);
    }
    public static void dfs(int at, int depth){
        if(depth == M){
            // 치킨거리 최소 계산
            int ans = 0;
            for(int i = 0; i < hsize; i++){
                int chicdis = Integer.MAX_VALUE;
                for(int j = 0; j < M; j++){
                    int cnum = alive[j];
                    chicdis = Math.min(chicdis, dis[i][cnum]);
                }
                ans += chicdis;
            }

            min = Math.min(min, ans);

            return;
        }
        for(int i = at; i < csize; i++){
            alive[depth] = i;
            dfs(i + 1, depth + 1);
        }
    }
}