알고리즘 문제 풀이/백준
[백준] 치킨 배달 - 15686번
h982
2021. 7. 8. 13:29
문제설명
https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
기본아이디어
맵에는 집과 치킨집이 존재한다. (1, 2로) 치킨집 중 M개를 선택했을 때 각 집들과의 거리의 합이 최소인 값을 구하면 된다.먼저 도시 정보에서 집과 치킨집 정보를 저장해두고 완전탐색으로 치킨집들 중 M개를 선택해서 집들과의 거리의 합을 계속해서 구하면서 최소값을 찾으면 된다.
구현코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(input.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][];
chicken = new ArrayList<>();
house = new ArrayList<>();
for(int i = 0; i < N; i++){
st = new StringTokenizer(input.readLine());
int[] temp = new int[N];
for(int j = 0; j < N; j++){
temp[j] = Integer.parseInt(st.nextToken());
if(temp[j] == 1){
house.add(new int[]{i, j});
}else if(temp[j] == 2){
chicken.add(new int[]{i,j});
}
}
map[i] = temp;
}
selected = new int[M];
min_dist = Integer.MAX_VALUE;
comb(0, 0);
System.out.println(min_dist);
}
static List<int[]> chicken;
static List<int[]> house;
static int N, M, min_dist;
static int[][] map;
static int[] selected;
static void comb(int idx, int cnt){
if(cnt == M){
int cal = calc();
if(cal < min_dist)
min_dist = cal;
return;
}
for(int i = idx; i < chicken.size(); i++){
selected[cnt] = i;
comb(i+1, cnt+1);
}
}
static int calc(){
int sum = 0;
for(int[] home : house){
int min = Integer.MAX_VALUE;
for(int select : selected){
int temp = Math.abs(home[0] - chicken.get(select)[0]) + Math.abs(home[1] - chicken.get(select)[1]);
if(temp < min)
min = temp;
}
sum += min;
}
return sum;
}
|
cs |
정리, 기억할 내용
1. 완전탐색으로 먼저 생각하고, 최적화 하자.
2. 문제의 입력값의 범위를 보고 완전탐색으로 가능할지 예측하자.