백준15686 : 치킨 배달
문제
NxN 배열 빈칸(0), 집(1), 치킨집(2) 이 있을 때, 이 중 치킨집을 M개만 남겼을 때, 최대가 되는 치킨거리를 구하는 문제. 치킨거리는 각 집에서 가장 가까운 치킨집의 거리를 모두 더한 값이다.
https://www.acmicpc.net/problem/15686
접근방법
치킨 리스트 중 M개를 선택한다. (combination 이용)
각 집 당, 고른 M개의 치킨집과의 거리를 비교해 가장 짧은 거리를 구하고, 이들을 모두 더한 치킨거리를 구한다.
최소의 치킨거리를 구한다.
치킨집 M개 고르기
치킨집을 ArrayList에 저장하고, combination 함수를 이용해 고를 치킨집의 인덱스를 구한다.
각 집의 치킨거리 구하기
모든 집과 모든 치킨집을 비교해 최솟값을 구하고, 각 집의 최솟값을 더해 치킨거리를 구한다.
소스코드
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);
}
}'알고리즘' 카테고리의 다른 글
| [JAVA] 백준 1018 : 체스판 다시 칠하기 (0) | 2019.01.16 |
|---|---|
| [JAVA] 백준 1120 : 문자열 (0) | 2019.01.13 |
| 백준16234 : 인구 이동 (0) | 2018.11.21 |
| 백준15684 : 사다리 조작 (0) | 2018.11.21 |
| 백준14889 : 스타트와 링크 (0) | 2018.11.16 |