백준 15686 치킨 배달 [JAVA]

15686번: 치킨 배달

 

풀이 방법

치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리의 최솟값을 구하는 문제였습니다.

 

도시의 정보가 주어질 때,

1인 경우에는 home 리스트에 2인 경우에는 chicken 리스트에 위치 정보를 넣어주었습니다.

 

최대 M개의 치킨 집을 선택하기 위해서 조합을 이용했고,

M개를 선택했을 때 check() 메서드에서 집의 위치로부터 치킨집들의 최소 거리를 구해주었습니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main_BJ_15686_치킨배달 {
    
    static class info{
        int x, y;
 
        public info(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
    }
    
    static int N,M, min=Integer.MAX_VALUE;
    static int [][] map;
    
    static ArrayList<info> chicken = new ArrayList<>();
    static ArrayList<info> choice = new ArrayList<>();
    static ArrayList<info> home = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][N];
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==2) chicken.add(new info(i,j));
                else if(map[i][j]==1) home.add(new info(i,j));
            }
        }
        
        comb(0,0);
        System.out.println(min);
    }
    
    public static void comb(int cnt, int start) {
        if(cnt==M) {
            check();
            return;
        }
        
        for(int i=start;i<chicken.size();i++) {
            choice.add(new info(chicken.get(i).x, chicken.get(i).y));
            comb(cnt+1, i+1);
            choice.remove(choice.size()-1);
        }
    }
    
    public static void check() {
        int distance, sum=0;
        for(int i=0;i<home.size();i++) {
            distance=Integer.MAX_VALUE;
            for(int j=0;j<choice.size();j++) {
                distance = Math.min(distance, Math.abs(home.get(i).x-choice.get(j).x)+Math.abs(home.get(i).y-choice.get(j).y));
            }
            sum+=distance;
        }
        
        min = Math.min(min, sum);
    }
 
}