백준15686 : 치킨 배달

백준15686 : 치킨 배달

문제

NxN 배열 빈칸(0), 집(1), 치킨집(2) 이 있을 때, 이 중 치킨집을 M개만 남겼을 때, 최대가 되는 치킨거리를 구하는 문제. 치킨거리는 각 집에서 가장 가까운 치킨집의 거리를 모두 더한 값이다.

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

접근방법

• 치킨 리스트 중 M개를 선택한다. (combination 이용)

• 각 집 당, 고른 M개의 치킨집과의 거리를 비교해 가장 짧은 거리를 구하고, 이들을 모두 더한 치킨거리를 구한다.

• 최소의 치킨거리를 구한다.

1. 치킨집 M개 고르기

   • 치킨집을 ArrayList에 저장하고, combination 함수를 이용해 고를 치킨집의 인덱스를 구한다.

2. 각 집의 치킨거리 구하기

• 모든 집과 모든 치킨집을 비교해 최솟값을 구하고, 각 집의 최솟값을 더해 치킨거리를 구한다.

소스코드

import java.util.*;
import java.io.*;
​
public class Main{
​
    static final int MAX = Integer.MAX_VALUE;
    static int N;
    static int M;
    static int map[][];
    static int min_dist;
    static ArrayList<Pos> home_list;
    static ArrayList<Pos> chicken_list;
​
    static class Pos{
        int x; int y;
        public Pos(int x, int y) {this.x = x; this.y = y;}
    }
​
    public static void combination(int arr[], int index, int n, int r, int target) {
        if(r == 0) {
            int cur_chick_dist = chickDist(arr);
            if(cur_chick_dist < min_dist)
                min_dist = cur_chick_dist;
        }else if(target == n) {
            return;
        }else {
            arr[index] = target;
            combination(arr, index+1, n, r-1, target+1);
            combination(arr, index, n, r, target+1);
        }
    }
​
    static int chickDist(int[] arr) {
        int sum = 0;   // M개 치킨집을 고른 맵에서의 치킨거리
​
        int[][] map_tmp = new int[N][N];
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++) {
                map_tmp[i][j] = map[i][j];
                if(map_tmp[i][j] == 2)
                    map_tmp[i][j] = 0; // 치킨집 초기화(아무 치킨집도 선택되지 않은 상태)
            }
​
        // 치킨집 선택
        ArrayList<Pos> tmp_chickList = new ArrayList();
        for(int i=0; i<arr.length; i++) {
            Pos chick_pos = chicken_list.get(arr[i]);
            map_tmp[chick_pos.x][chick_pos.y] = 2;
            tmp_chickList.add(chick_pos);
        }
​
        // 각 사람당 가장 가까운 치킨집과의 거리 계산 후 합산
        for(int i=0; i<home_list.size(); i++) {
            int person_min_dist = MAX;
            for(int j=0; j<M; j++) {
                int cur_dist = 0;
                cur_dist = Math.abs(home_list.get(i).x - tmp_chickList.get(j).x)
                        + Math.abs(home_list.get(i).y - tmp_chickList.get(j).y);
                if(cur_dist < person_min_dist)
                    person_min_dist = cur_dist;
            }
            sum += person_min_dist;
        }
​
        return sum;
    }
​
    public static void main(String[] args) throws IOException {
​
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
​
        String input[] = in.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        map = new int[N][N];
        home_list = new ArrayList();
        chicken_list = new ArrayList();
​
        for(int i=0; i<N; i++) {
            String line[] = in.readLine().split(" ");
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(line[j]);
                if(map[i][j] == 1)
                    home_list.add(new Pos(i, j));
                else if(map[i][j] == 2)
                    chicken_list.add(new Pos(i,j));
            }
        }
​
        min_dist = MAX;
        combination(new int[M], 0, chicken_list.size(), M, 0);
​
        System.out.println(min_dist);
​
​
    }
​
}